Высказываний). Построение таблиц истинности

Символы , &, ∨, ⇒, ≡ называются пропозициональными связками.

Заглавные буквы алфавита (А, В, С,...) и те же буквы с числовыми индексами

(А1, А2,..., В1, В2,..., С1, С2,...) называются пропозициональными буквами.

Считается, что каждая пропозициональная буква может принимать значение

И либо Л.

Выражением называется конечная последовательность определенных

символов. Например, ∨ А& ∨ В - выражение, построенное из символов ∨, &, А и

В, а? §!! - выражение, построенное из символов?, § и!.

Пропозициональная форма представляет собой выражение, полученное

по некоторым правилам из пропозициональных букв с помощью

пропозициональных связок.

Индуктивное определение пропозициональной формы:

1) все пропозициональные буквы суть пропозициональные формы,

2) если А и В пропозициональные формы, то ( А), (А & В), (А ∨ В), (А ⇒ B), (А ≡ B)

тоже пропозициональные формы,

3) только те выражения являются пропозициональными формами, для

которых это следует из пп.1, 2.

Примеры пропозициональных форм: A, ( В), ((А& В)⇒ ( C)), ( ((А)∨ В)≡ С).

Пропозициональные формы часто называют формулами логики

высказываний.

Жирные заглавные буквы латинского алфавита (А, В, C,...) или те же буквы с

числовыми индексами (А 1, А 2 ,..., В 1, В 2 ,..., С 1, С 2 ,...) употребляются для

обозначения произвольных пропозициональных форм, тогда как обычное

написание этих букв применяется лишь для пропозициональных букв.

Истинностной функцией от n аргументов называется n-аргументная функция,

принимающая одно из двух значений: И либо Л, когда ее аргументы

пробегают те же значения.

Составное (сложное) высказывание, образованное с помощью введенных

операций , &, ∨, ⇒, ≡ будет истинным либо ложным в зависимости от

значений исходных высказываний. Следовательно, полученное составное

высказывание порождает некоторую истинностную функцию.

Как определено выше, каждая пропозициональная буква может принимать

значения И либо Л. Будем считать, что пропозициональные формы ( А),

(А& В), (А∨ В), (А⇒ В) и (А ≡ Β) имеют те же таблицы истинности, что и

обозначаемые таким образом высказывания (см.§1). Тогда каждому

распределению (истинностных) значений И и Л пропозициональных букв,

входящих в пропозициональную форму, соответствуют согласно таблицам

истинности для пропозициональных связок некоторые истинностные значения

этой пропозициональной формы.

Таким образом, каждая пропозициональная форма порождает некоторую

функцию, принимающую значение Л или И в зависимости от истинностных

значений пропозициональных букв в нее входящих, следовательно, каждая

пропозициональная форма порождает некоторую истинностную функцию.

Заметим, что пропозициональная форма не является высказыванием. По

определению пропозициональная форма - это выражение, построенное из

пропозициональных букв, т.е. букв А, В, С,..., А1, А2,..., В1, В2,..., С1, С2,... с

помощью пропозициональных связок согласно правилам 1), 2), 3) и ничего

более. В частном случае пропозициональные буквы могут обозначать

высказывания, пропозициональные связки - логические операции, тогда

пропозициональная форма будет обозначать некоторое высказывание.

Истинностное значение полученного высказывания можно определить с

помощью таблиц истинности.

Так как добавление каждой новой пропозициональной буквы увеличивает

количество строк в таблице истинности вдвое, то пропозициональная форма,

содержащая n различных пропозициональных букв, имеет таблицу

истинности с 2n строками. Например, для формы (((А& В)∨ С)⇒ А) имеем

следующую таблицу истинности.

А B C (A& B) ((А& В)∨

С)

(((А& В)∨

С)⇒ А)

Л Л Л Л Л И

Л Л И Л И Л

Л И Л Л Л И

Л И И Л И Л

И Л Л Л Л И

И Л И Л И И

И И Л И И И

И И И И И И