Элементы математической логики. Нормальные виды формул. Совершенные нормальные формы

ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ.

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

Определение: Отрицанием высказывания pназывают высказывание, которое истинно тогда и только тогда, когда pложно. Обозначается: или .

Определение: Конъюнкцией высказываний P и Q называется высказывание истинное тогда и только тогда, когда оба высказывания истинные. Обозначается: .

Определение: Дизъюнкцией высказываний P и Q называется высказывание, которое ложно тогда и только тогда, когда оба высказывания ложны. Обозначается:

Определение: Импликацией двух высказываний P и Q называется высказывание, которое ложно тогда и только тогда, когда P истинно, а  Q – ложно. Обозначается: , , .

Определение: Эквиваленцией двух высказываний P и Q называется высказывание, которое истинно тогда и только тогда, когда истинностные значения P и Q совпадают. Обозначается: , .

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

Алфавит логики высказываний состоит из:

1)  Высказывательных переменных x₁, x₂,x₃  …. x_n

2)  Логических символов , , , ,

3)  Скобок

Определение: Формулой называется:

1)  Любая высказывательная переменная

2)  Если x₁ и x₂ – формулы, то x₁, x₁x₂, x₁x₂, x₁x₂, x₁x₂ также называется формулой.

Упорядоченный набор высказывательных переменных x₁, x₂, x₃  …. x_к называется списком переменных формулы А. если все переменные формулы А содержаться в этом наборе.

А =

Список: <x₁, x₂,x₃, x₄ >

Замечание: В списки переменных формулы А часть элементов может быть фиктивной, т.е. входить явно в формулу А.

Определение: Оценкой списка переменных называется сопоставление каждой переменной списка некоторого истинностного значения.

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

Истинностная функция представляется таблицей истинности.

Пример: Составить таблицу истинности для

А: <x_i1, x_i2, x_i3 … x_ik>

Определение: Формула А называется тавтологией, если на любых оценках списка переменных она принимает значение «истина»

Определение: Формула А называется тождественно ложной, если на  любых оценках списка переменных она принимает значение «ложь».

Определение: Формула А называется выполнимой, если на некоторой оценке списка переменных она принимает значение «истина».

Определение: Формула А называется опровержимой, если на некоторой оценке списка переменных она принимает значение «ложь».

Определение: Пусть А и В – две формулы зависящие от одного и того же списка переменных. Они называются равносильными, если на любом наборе они принимают одинаковое значение. АВ.

Утверждения:

1)  А - тавтология тогда и только тогда, когда А не является опровержимой

2)  А - тождественно ложно тогда и только тогда, когда А не является выполнимой