§2. Формулы алгебры логики. Таблицы истинности.

2.1. Формулы алгебры логики. Из пропозицианальных переменных a, b, c ..., принимающих значения 1 или 0, с помощью знаков: , , , , , |, ,  и с помощью скобок (как это делается в алгебре) можно строить и новые выражения, называемые формулами, которые определяются следующим образом:

а) всякая пропозициональная переменная есть формула;

б) Если F₁ и F₂ — формулы, то выражения F₁, (F₁F₂), (F₁F₂), (F₁F₂), (F₁F₂), (F₁|F₂), (F₁F₂), (F₁F₂) также являются формулами;

в) других формул, кроме построенных по правилам двух предыдущих пунктов, нет.

Обычно внешние скобки у формулы не пишут.

Формулы будем обозначать через заглавные буквы латинского алфавита: A, B, C, ... , A₁, A₂, …. Тот факт, что формула А составлена из пропозициональных переменных а₁, а₂, …, а_п обозначается через А(а₁, а₂, …, а_п).

Подформулой формулы называется всякая её часть, которая сама является формулой.

Например выражение: a((b)(ac)) является формулой. Напомним, что знаки , , , |, , , ,  называются логическими операциями. Сначала логические операции выполняются в скобках, затем вне скобок. Можно сэкономить число скобок, если считать, что при отсутствии скобок логические операции выполняются в следующем порядке: , , |, , , , , . В силу этого соглашения предыдущую формулу можно записать в виде: a(bbc). Заметим, что указанную пару скобок уже опустить нельзя.

Упражнение 2.1.Определите, является ли последовательность символов формулой:

а) ((p&q)r)  s;

б) ((pq)r)  (pr);

в) ((pq)  (r(qs)));

г) ((pq)  (rs));

д) (p  (q&rp));

е) ((p&q)  (p(rs)));

ж) ((p&(qr))(( pr) q)).

Решение. а) Данная последовательность не является формулой. В самом деле, пропозициональные переменныеp,q, иrсогласно п. а) определения формулы являются формулами. Следовательно, согласно п. б) этого определения последовательность (p&q) будет формулой. Но следующая последовательность ((p&q)r) формулой не будет, так как входящие в нее формулы (p&q) иrне соединены ни одним из допустимых символов: &,,,, |,,. Поэтому и данная последовательность формулой не является.

ж) Согласно п. а) и б) определения пропозициональные переменные p,qиrи выраженияp,q, (q r), (pr) будут формулами. Далее формулами будут выражения (p&(qr)), ((pr)q)). Наконец, выражение ((p&(qr))((pr)q)), представляющее собой данную последовательность, также является формулой.

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

а) p  q& r  s;

б) p q  r pr;

в) p & q  r;

г) p q r&q;

д) pqr &q.

Решение. д) Вот эти формулы (внешние скобки опущены):

(pq)(r &q );(p((qr)&q));

(p(qr))&q((pq)(r &q));

(p(qr))&q ;((p(qr))&q);

(p(qr))&q;(p((q r)&q));

((pq)r)&q;(pq)(r &q);

((p(qr))&q);p((qr) &q );

(p((q r)&q));p((qr) &q );

(p(q(r &q)));(p(qr)) & q;

(p(q (r &q))).

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

а) ((p q) &r)(((p q)p)r);

б) ((p q)r) & (p(qr));

в) (pq)((pq)(p&q));

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

2.2. Таблицы истинности. Для нахождения значений формулы строится её таблица истинности. Заголовки таблицы представляют собой всевозможные подформулы формулы, образованные её логическими операциями в порядке их выполнения. Заголовки строк  это всевозможные наборы строк значений пропозициональных переменных. На пересечении строки и столбца стоит значение соответствующей подформулы на соответствующем наборе переменных. Всего можно составить 2^п всевозможных наборов из 0 и 1, значит, и строк у таблицы будет столько же. Обычно наборы формируют следующим образом. Упорядочим переменные, входящие в формулу: (а, b, …, ), (а₁, а₂, …, а_п), (x₁, x₂, …, x_п) и т.д. (в зависимости от того, как они обозначены). Каждый упорядоченный набор представляет собой некоторую последовательность из нулей и единиц. Поэтому его можно рассматривать как некоторое число, записанное в двоичной системе. Располагая наборы в порядке возрастания соответствующих чисел, мы получим упорядочение наборов значений в так называемом лексикографическом порядке. Такое расположение удобно в первую очередь для того, чтобы безошибочно перечислить их всех.

Таблица истинности формулы А=a(bac) выглядит следующим образом

a	b	c	b	ac	bac	A(a, b, c)
0	0	0	1	0	0	1
0	0	1	1	0	0	1
0	1	0	0	0	1	1
0	1	1	0	0	1	1
1	0	0	1	0	0	0
1	0	1	1	1	1	1
1	1	0	0	0	1	1
1	1	1	0	1	0	0

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

a	b	c	a		(b		ac)
0	0	0		1	1	0	0
0	0	1		1	1	0	0
0	1	0		1	0	1	0
0	1	1		1	0	1	0
1	0	0		0	1	0	0
1	0	1		1	1	1	1
1	1	0		1	0	1	0
1	1	1		0	0	0	1

Формула содержащая хотя бы одну логическую операцию называется сложной (или составной). Например, формула рассмотренная в таблице 1, является составной. О составной формуле aa или формуле aa говорят, что буква a имеет два вхождения в каждую из них.

Особый интерес представляют формулы, которые принимают только значения “истина”  1,  или только значения “ложь”  0.

Формулы

a a, aba (1)

принимают только значения 1, а формулы

a a, aba (2)

принимают только значения 0.

Определение 5. Пусть А — произвольная формула. Если формула А при всевозможных логических значениях входящих в нее пропозициональных букв принимает только истинное значение 1, то она называется тавтологией, если же она принимает только ложное значение 0, то она называется противорачием. Если формула А, хотя бы для одного набора логических значений входящих в нее пропозициональных букв принимает значение 1 (значение 0), то она называется выполнимой (опровержимой).

Например, формулы (1) являются тавтологиями, формулы (2) — противоречиями, а формула ab является одновременно выполнимой и опровержимой.

Итак, чтобы проверить, является ли данная формула А тавтологией, достаточно для нее составить таблицу истинности. Если формула принимает только значения 1, то она является тавтологией. Если же хотя бы один раз она принимает значение 0, то она не является тавтологией.

Упражнение 2.4.Составьте таблицы истинности для следующих формул и укажите, какие из формул являются выполнимыми, какие — опровержимыми, какие тождественно-истинными (тавтологиями) и какие тождественно ложными (противоречиями):

а) (pq)((pq)p);

б) ((pq)p)q;

в) p&(qp))|((qp)q);

г) ((p&q)q)(pq);

д) p&(q(pq));

е) ((pq)q)q;

ж) ((p q)q)&(pq).

Решение. ж) Обозначим формулу черезF(q, p). Составим таблицу истинности данной формулы:

p	q	q	pq	(pq)q	p	pq	F(q, p)
0	0	1	1	0	1	1	0
0	1	0	0	1	1	1	1
1	0	1	1	0	0	0	0
1	1	0	1	1	0	1	1

Из построенной таблицы истинности видно, что данная формула выполнима, так как, например, при p=1иq=0имеемF(q, p)=F(0, 1)=1. Аналогично, формула является опровержимой, так как, например,F(0, 0)=1. Следовательно, формула не является ни тавтологией, ни тождественно ложной формулой.

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

Упражнение 2.5.Докажите, что следующие формулы выполнимы:

а) (pp);

б) (pq)(qp);

в) (q(p&r))&((p r)q);

г) ((p q)r)&q;

д) (p&q)((rq)(q&q));

Решение. д) Заключение второй импликации есть, очевидно, тождественно ложная формула. Поэтому если посылкаrqвторой импликации превратится при некоторой подстановке в ложное высказывание, то вся вторая импликация станет истинным высказыванием, и, следовательно, вся данная импликация превратится в истинное высказывание независимо от того, в какое высказывание обратится посылкаp&qвсей данной импликации. Посылкаrqвторой импликации обращается в ложное высказывание, когда вместо переменных rи qподставляются ложные высказывания. Итак, данная формула выполнима, поскольку она обращается в истинное высказывание, если вместо rи qподставить ложные высказывания, а вместоp— произвольное высказывание (его истинность в данном случае не повлияет на истинность всего высказывания).

Надо отметить, что задачу можно решить, построив таблицу истинности. Согласно определения выполнимой формулы, эта формула должна принимать как значения 1, так и значения1.

2.3. Законы логики. Наиболее часто используемые в логике и в математике тавтологии называются законами логики. Приведем некоторые из них и укажем для некоторых из них названия:

1) a(ab)b (закон заключения);

2) ((ab)(bc))(ac) (закон цепного заключения);

3) aba;

4) abb;

5) (ab)ab;

6) (ab)ab;

7) aa (закон двойного отрицания);

8) (ab)(ba) (закон контрапозиции);

9) (ab)(ab);

10) (ab)((ab)(ba));

11) (a(bc)(bc))(ac);

12) ((bc)(bc))b;

13) (aa)a;

14) (aa)a;

15) aa (закон исключённого третьего);

16)  (aa) (закон отрицания противоречия);

17) (ab)(ba);

18) (a(bc))((ab)c);

19) (ab)(ba);

20) (a(bc))((ab)c);

21) (a(bc))((ab)(ac));

22) (a(bc))  ((ab)  (ac));

23) aa;

24) aa;

25) a0a;

26) a00;

27) a11;

28) a1a.

Чтобы убедиться в том, что приведенные формулы являются тавтологиями, достаточно для каждой из них составить истинностную таблицу и убедиться, что каждая из них принимает только истинное значение. Например истинностная таблица для формулы aa имеет вид:

a	a	aa
1	0	1
0	1	1

Упражнение 2.6.Доказать, что приведённые выше формулы 2) — 28) являются тавтологиями.

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

а) a(ba);

б) (ab)((a(ba))(ac));

в) a(b(ab));

г) a(ab);

д) (ab)a;

е) (a(bc))((ab)(ac));

ж) ((ab)(ab))a;

з) (ac)((bc)((ab)c;

и) (ab)((ab)a);

к) (ab)(ba);

л) (ab)((ba)(ab));

м) ((a(ba)a;

н) (ab)(ab);

о) (ac)((ab)(cb));

п) (a(bc))((ab)(ac));

р) (a(bc))((ab)c).

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

Высказывание (в каком-либо естественном языке, например, в русском), которое получается из какой-либо тавтологии посредством подстановки высказываний (или даже некоторых предложений) вместо пропозициональных переменных, при условии, что все вхождения одной и той же переменной заменяются одним и тем же высказыванием, называется логически истинным. О таком высказывании можно сказать, что оно истинно в силу одной только своей структуры. Примером логически истинного высказывания может служить высказывание русского языка “идет дождь или не идет дождь”, которое получается из тавтологии aa подстановкой вместо буквы a предложения “идет дождь”.

Заметим, что следует отличать истинное высказывание от логически истинного высказывания. Например, высказывание “2·2=4” является истинным, но не является логически истинным. Высказывание “если 2·2=4, то 2·2=4” или же высказывание “если 2·2=5, то 2·2=5” являются логически истинными. Они получаются из тавтологии aa. Эти высказывания можно считать также истинными. Вообще, всякое логически истинное высказывание можно считать истинным. Например, высказывание “идет дождь или не идет дождь” истинно, так как оно логически истинно.

Приведём теперь пример противоречия. Формула aa является противоречием. Действительно, её истинностная таблица имеет вид:

a	a	aa
1	0	0
0	1	0

Высказывания, которые получаются из противоречия аналогичным образом, называются логически ложными. Подставим, например, в эту формулу вместо переменной a предложение “дождь идёт”, получим высказывание “идёт дождь и не идёт дождь”, которое является логически ложным. Всякое логически ложное высказывание можно считать просто ложным.