Дискретная математика (стр. 3 )

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

1   Элементарные высказывания – а, b, с, … 1, 0.

2   Высказывательные переменные – х, у, z, … – формулы (элементарные формулы).

3   Если F и F – формулы, то

, , (F F ), (F F ), (F ~ F ), (F F )

также формулы.

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

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

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

б) конъюнкция «сильнее» дизъюнкции, а обе они «сильнее» эквиваленции и импликации (т. е. исполняется сначала более сильная операция);

в) импликация «сильнее», чем эквиваленция;

г) конъюнкцию можно обозначать знаком «∙» или знак конъюнкции опускать.

Итак:

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

2  Ввиду насыщенности формул скобками и их трудночитаемости общеприняты следующие соглашения об упрощении записи формул:

а)  наружные скобки в записи формул можно опускать;

б)  операция конъюнкции «сильнее» операции дизъюнкции, а обе они «сильнее» операций эквиваленции и импликации, поэтому часть скобок, определяющих порядок действий, можно соответственно этому опускать;

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

г)  конъюнкцию можно обозначать знаком «·» либо знак конъюнкции опускать.

Пример. Дана формула

(((аb))с)((а)а).

Ее упрощенная запись имеет вид:

аbс(а)·а.

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

Отметим теперь, что справедливы следующие утверждения:

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

2  Две формулы алгебры высказываний и

называют равносильными, если

(х, х,…, х ) (х, х,…, х ).

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

Пример. Применяя равносильные преобразования, доказать соотношение:

≡ bа.

Решение

Применяя одну из формул законов де Моргана к левой части данного соотношения, имеем:

≡ ≡ а.

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

bа ≡ а ≡ а,

т. е. левая и правая части данного соотношения равносильны.

Определение. Пусть – формула алгебры высказываний. Двойственной к ней будем называть формулу F*(х, х,…, х ), определенную следующим образом:

F*(х, х, …, х )

Из закона двойного отрицания следует, что (F*)* F.

Справедлива также следующая теорема.

Теорема (принцип двойственности для булевых формул)

Двойственная к булевой форм на 0, на , на и сохранением структуры формулы (т. е. соответствующего порядка действий).

Пример. (x·z)* (x)·z.

Скобка в правой части поставлена для сохранения структуры формулы.

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

n-местным предикатом называется логическая функция переменных произвольной природы – х, х,… х. При этом под логической функцией n переменных понимается определенным образом установленное соответствие между любым набором значений этих переменных (х, х,… х) из некоторой области и высказыванием, значение истинности которого либо 1, либо 0.

Поскольку любой n-местный предикат устанавливает соответствие между областью значений n переменных и множеством высказываний (т. е. отображает область n переменных во множество высказываний), в котором введены логические операции, то эти операции естественным образом определяются и для предикатов. Для предикатов вводятся еще две логические операции, уменьшающие их местность (т. е. количество переменных), – фиксация значений переменных и навешивание кванторов.