Это сложное высказывание составлено из элементарных с помощью уже известных операций импликации и конъюнкции, и для него можно составить таблицу истинности исходя из определений (таблиц) этих операций.

Как видно из таблицы, высказывание (2), а, следовательно, и (1) истинно тогдаи только тогда, когдаp иq обаистинны илиобаложны.

Сложное высказывание «p, если и только если (тогда и только тогда, когда; необходимо и достаточно) q» мы назовем эквиваленцией и обозначим p q .

Сформулируем строгое определение.

Эквиваленцией двух высказываний p и q называется такое высказывание, которое истинно тогда и только тогда, когда высказывания p и q или оба истинны, или оба ложны.

Это определение может быть записано в виде соответствующей таблицы истинности.

Логические операции хорошо ассоциируются с операциями над множествами. Для понимания этого соответствия следует интерпретировать логическое значение «истина» как «принадлежит», а значение «ложь» — как «не принадлежит». Тогда дизъюнкция соответствует объединению (двух множеств), конъюнкция — пересечению (двух множеств), отрицание — дополнению (данного множества до U). Предоставим читателю проверить, как записать в терминах теории множеств остальные логические операции (импликацию и эквиваленцию).

§ 4. Формулы и функции логики высказываний

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

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

— 23 —

Буквы p, q, r,... применяются не только для обозначения определенных высказываний, но и в качестве переменных для высказываний. То есть формула выражает логическую структуру любого высказывания из всех, имеющих общую структуру. Высказывательные переменные принимают лишь два значения: И и Л.

Определение:

(a) p, q, r, ...,p1, p2 , ... , а также И и Л — формулы (элементарные формулы);

(b) если ϕ1 и ϕ2 — формулы, то

¬ϕ, (ϕ1 ϕ2 ), (ϕ1 ϕ2 ), (ϕ1 ϕ2 ) (ϕ1 ϕ2 ) — формулы;

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

Для упрощения записи формул примем следующие соглашения:

1)логические операции в порядке старшинства (¬, , , , ) учитывать при расстановке скобок;

2)опускать внешние скобки, т. е. скобки, которые заключают внутри себя все остальные символы, составляющие формулу;

3)по возможности опускать знак конъюнкции.

Например, записанная без учета этих соглашений формула

((p q) r) ((¬p q) ¬r))

будет выглядеть после упрощений так:

pq r (¬p q ¬r).

Пусть ϕ1 (p1, p2 , ... pn ) — формула логики высказываний, содержащая переменные p1, p2 , ... pn . Так как каждая переменная pi может принимать лишь два значения — И и Л, то для n переменных существует 2n вариантов различных значений.

Сама формула ϕ(p1, p2 , ... pn ) также может иметь лишь два значения — И или Л, поэтому можно считать, что формула определяет некоторую функцию с областью определения {И, Л}n и областью значений {И, Л}. Такая функция (отображение) всегда может

— 24 —

быть задана с помощью конечной таблицы истинности, содержа-

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

Функция типа {И, Л}n → {И, Л}, т. е. отображение множества

n-ок элементов из {И, Л} во множество {И, Л} называется n-мест- ной функцией логики высказываний или высказывательной функцией n высказывательных аргументов.

§ 5. Равносильные формулы

p	q	r	pq	pq r	¬r	p¬r	¬q	p¬r ¬q
И	И	И	И	И	Л	Л	Л	И
Л	И	И	Л	И	Л	Л	Л	И
И	Л	И	Л	И	Л	Л	И	И
И	И	Л	И	Л	И	И	Л	Л
И	Л	Л	Л	И	И	И	И	И
Л	И	Л	Л	И	И	Л	Л	И
Л	Л	И	Л	И	Л	Л	И	И
Л	Л	Л	Л	И	И	Л	И	И

Составим таблицу истинности для двух формул: pq r (1) и p¬r ¬q (2).

Мы видим, что столбцы значений формул (1) и (2) совпадают, т. е. эти формулы принимают равные значения (обе И или обе Л) при любом наборе значений переменных p, q, r. Поэтому они (формулы) определяют одну и ту же функцию логики высказываний (в данном случае одну и ту же трехместную функцию).

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

— 25 —

Равносильность формул обозначим значком ≡.

Отношение равносильности (эквивалентности) формул удовлетворяет трем законам:

1)для любой формулы ϕ ≡ ϕ (рефлексивность);

2)если ϕ1 ≡ϕ2 , то ϕ2 ≡ϕ1 (симметричность);

3)если ϕ1 ≡ϕ2 и ϕ2 ≡ϕ3 , то ϕ1 ≡ϕ3 (транзитивность) для лю-

бых формул ϕ1, ϕ2 и ϕ3 .

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

Приведем наиболее важные равносильные формулы.

1)p ≡ ¬ (¬p) (закон двойного отрицания);

2)pq ≡ qp (коммутативность конъюнкции);

3)p q ≡ q p (коммутативность дизъюнкции);

4)p(qr) ≡ (pq)r (ассоциативность конъюнкции);

5)p (q r) ≡ (p q) r (ассоциативность дизъюнкции);

6)p(q r) ≡ pq pr (дистрибутивность конъюнкции относительно дизъюнкции);

7)p qr ≡ (p q)(p r) (дистрибутивность дизъюнкции от-

носительно конъюнкции);

8)pp ≡ p;

9)p p ≡ p;

10)p ¬p ≡ И (закон исключения третьего);

11)p ¬ p ≡ Л (закон противоречия);

12)pИ ≡ p;

13)p И ≡ И;

14)pЛ ≡ Л;

15)p Л ≡ p;

16)¬(pq) ≡ ¬p ¬q (1-й закон де Моргана);

17)¬(p q) ≡ ¬p¬q (2-й закон де Моргана);

18)p q ≡ ¬p q;

19)p q ≡ (p q)(q p).

— 26 —