Понятия формулы логики высказываний

1. Символы простых высказываний являются формулами

2. Если F и G – формулы, то формулами будут `F, FÙG, FÚG, F®G, F«G

3. Других формул нет. Это означает, что формулами могут быть только такие, которые либо 1) либо 2).

4. О простых формулах, входящих в составную, говорят, что они содержатся в ней, и называют их её простыми компонентами. Последовательность операций устанавливается скобками. Поскольку большое число скобок затрудняет чтение, то между операциями устанавливается иерархия: отрицание предшествует всем операциям, затем конъюнкция (символÙ часто опускается), дизъюнкция, импликация, двойная импликация.

Например:

(`aÙbÚc) означает (((`a)Ùb)Úc)

(a«bÙc) означает (a«(bÙc)

(a«b®c) означает (a«(b®c))

Истинностные таблицы.

Выше были определены основные логические операции и приведены их истинностные таблицы, которые фактически являются определениями этих операций. С помощью этих таблиц можно составить таблицы истинности для любой формулы. Если формула F содержит n простых компонентов, каждый из которых принимает два значения: 0 и 1, то истинностная таблица формулы F содержит 2ⁿ наборов. Для каждого из них формула F принимает значение или 0 или 1. Это и есть истинностная таблица формулы F.

Замечания

1. Хотя 2ⁿ наборов значений простых компонент, входящих в формулу F, можно располагать в любом порядке в таблице истинности, мы, для определенности будем использовать двоичную запись порядкового номера набора. Например, для n=3 это будет следующий порядок: 000, 001, 010, 011, 100, 101, 110, 111.

2. Условимся опускать внешние скобки в формуле. Например, F=ab®bÚc вместо F=(ab®`bÚc).

3. Будем говорить, что простая компонента входит в формулу F несущественно (фиктивно), если истинностное значение формулы F не зависит от истинностного значения этой компоненты. Так, таблица истинности формулы F=abÚa имеет вид:

а	b	abÚa

Сравнивая первую и вторую, а затем третью и четвёртую строки, замечаем, что F зависит только от значения, принимаемого компонентой а, т.е. b – несущественная компонента.

4. Кроме основных 5 логических связок, иногда используются и другие. Например, p¯q переводится как “ни p,ни q”, и формула p¯q принимает значение 1 только тогда, когда p=q=0.

Упражнения.

1. Составить таблицы истинности для следующих формул:

a. p®qÚr

b. pÚq«qÚp

c. (p®(q®r))®((p®q)®(p®r))

d. (p®q)«(`pÚq)

e. (p®q)®((q®r)®(p®r))

f. (p®q)®r