2. Формулы логики высказываний

Прописными буквами латинского алфавита А, В, …, Х, У, Z (возможно с индексами) будем обозначать пропозициональные (высказывательные) переменные. Значениями пропозициональных переменных являются элементарные высказывания.

Формулой (пропозициональной) логики высказываний называется выражение, построенное из пропозициональных переменных с помощью логических связок по следующим правилам:

1. Любая пропозициональная переменная, а также символы истины «1» и лжи «0» есть формула.

2. Если А и В – формулы, то , (А  В), (А  В), (А  В), (А  В) – тоже формулы.

3. Других формул нет.

В дальнейшем формулу логики высказываний будем называть формулой.

Пример. Представить формулой следующее высказывание: «Если идет дождь, то надо взять зонт».

Решение. Высказывание состоит из двух простых: А – «Идет дождь», В – «Надо взять зонт». Тогда формула имеет вид: (А  В).

Для сокращения записи формул условимся в формулах опускать внешние скобки. Условимся также о приоритете логических связок, в соответствии с которым отрицание «» имеет высокий приоритет и выполняется прежде всего. Следующий по рангу приоритет (по убыванию) имеют конъюнкция «», дизъюнкция «», импликация «», эквиваленция «». Зная приоритет логических связок, можно опускать те пары скобок, без которых ясен порядок выполнения логических связок. Тогда, например, формулу (А  В) можно записать в виде А  В, формулу (((А  В)  С)  D) – в виде А  В  С  D.

Любая формула логики высказываний задает форму для получения сложных высказываний. Пусть, например, задана формула А  В  С. Тогда, если пропозициональным переменным А, В, С придать значения элементарных высказываний «2  2 = 4», «3 + 5 = 8», «10 – 3 = 5» соответственно, то получим высказывание «если «2  2 = 4» и «3 + 5 = 8», то «10 – 3 = 5»». Если учесть, что первые два высказывания имеют логическое значение «истина» (1), а третье – «ложь» (0), тогда, используя логические операции, можно сделать заключение, что полученное высказывание имеет логическое значение «ложь» (0). Если вместо пропозициональных переменных А, В, С подставить другие элементарные высказывания, то получим новое высказывание, которое будет иметь свое логическое значение 0 или 1.

Замечание. Логические символы «1» и «0» являются пропозициональными константами, им соответствуют любое истинное и любое ложное высказывание соответственно.

Таким образом, мы подошли к понятию логического (истинностного) значения формулы.

Логическим значением пропозициональной переменной будем называть логическое значение элементарного высказывания, которое принимает пропозициональная переменная. Логические значения пропозициональных переменных «1», «0».

Логическое значение формулы есть логическое значение сложного высказывания, полученного из формулы заменой входящих в нее пропозициональных переменных элементарными высказываниями.

Логическое значение формулы однозначно определяется логическими значениями входящих в нее пропозициональных переменных и логических операций.

Все логические значения формулы в зависимости от логических значений входящих в нее пропозициональных переменных могут быть полностью описаны с помощью таблицы истинности. Каждому варианту логических значений пропозициональных переменных соответствует отдельная строка таблицы истинности. Если в формуле имеется n различных пропози-циональных переменных, то для них возможны 2ⁿ различных вариантов логических значений. Таблица истинности для такой формулы содержит 2ⁿ строк. Для облегчения построения таблицы истинности в нее включают столбцы, соответствующие промежуточным вычислениям.

Пример. Определить всевозможные логические значения формулы Z = = А   .

Решение. Задача может быть решена путем перебора всевозможных логических значений переменных А и В с помощью таблицы истинности.

Расширенная таблица истинности для нашей формулы Z содержит 2² = 4 строк и имеет вид:

А	В		А 		Z
1	1	0	0	0	0
0	1	0	0	1	1
1	0	1	1	0	1
0	0	1	0	1	1

Множество всех формул логики высказываний разбивается на три непересекающихся подмножества (класса):

1) тождественно ложные формулы (противоречия), принимающие только логическое значение «0» при любых логических значениях входящих в них пропозициональных переменных;

2) тождественно истинные формулы (тавтологии), принимающие только логическое значение «1» при любых логических значениях входящих в них пропозициональных переменных;

3) формулы, принимающие оба логические значения «0» и «1» на разных наборах логических значений пропозициональных переменных.

Очевидно, что если F – формула противоречия (тавтология), то ее отрицание – тавтология (противоречие). Например, формула Х  У  Х является тождественно истинной (тавтология).