§2. Формулы логических высказываний и таблицы истинности.

Пусть p, q, r, s – это произвольные элементарные высказывания. С логической точки зрения это переменные, принимающие истинное или ложное значение. При помощи логических операций можно получить сложные (или еще более сложные) высказывания. Зная истинное значение элементарных высказываний, легко установить значение составленных сложных высказываний.

Определение формулы логики высказываний.

1. Символы логических констант И и Л являются формулами.

2. Каждое элементарное высказывание также является формулой.

3. Если ₁ и ₂ являются формулами, то формулами будут являться их отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция.

4. Других формул в логике высказываний нет.

Другими словами, формулой логики высказываний называют конечную последовательность букв, знаков логических операций и скобок, выражающих структуру высказываний. Скобки в формуле могут указывать на порядок следования операций. Для упрощения записи и уменьшения числа скобок принят следующий порядок:

1. отрицание;

2. конъюнкция;

3. дизъюнкция;

4. импликация;

5. эквиваленция.

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

1. В первой строке таблицы выписываются все переменные высказывания и все подформулы, начиная с простых и заканчивая самой формулой. Для каждой записи заготавливается столбец.

2. Высказывательным переменным даются все возможные наборы значений по правилу:

   • для первой переменной половина строчек ИСТИНА, половина – ЛОЖЬ;

   • для второй – ¼ строчек ИСТИНА, ¼ строчек ЛОЖЬ, ¼ строчек ИСТИНА, ¼ строчек ЛОЖЬ;

   • для третьей - ⅛ строчек ИСТИНА, ⅛ строчек ЛОЖЬ и т.д.

   • для последней переменной значения задаются чередованием И, Л, И, Л.

   • Количество строк в таблице – 2ⁿ, где n – число элементарных высказываний.

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

Запишем таблицы истинности для логических операций:

§3. Равносильность формул логики высказываний.

Определение: Две формулы логики высказываний называются равносильными, если при одних и тех же наборах значения переменных они принимают одинаковое значение. Равносильность обозначается .

Основные равносильности, выражающие свойства логических операций, даны в таблице.

Таблица основных равносильностей

конъюнкция	дизъюнкция
Коммутативность
1)	1’)
Ассоциативность
2)	2’)
Рефлексивность
3)	3’)
Дистрибутивность
4)	4’)
Законы поглощения
5)	5’)
Законы де Моргана
6)	6’)
Законы взаимодействий с истиной и ложью
7)	7’)
8) Закон противоречия	9) Закон исключенного третьего
10) Закон двойного отрицания
11) Закон исключения импликации

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

Докажем одно из свойств:

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

Например: