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

Страницы работы

Содержание работы

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

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

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

и

л

л

и

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

P

Q

л

л

л

и

л

л

л

и

л

и

и

и

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

P

Q

л

л

л

и

л

и

л

и

и

и

и

и

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

P

Q

л

л

и

и

л

л

л

и

и

и

и

и

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

P

Q

л

л

и

и

л

л

л

и

л

и

и

и

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

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

1)  Высказывательных переменных x1, x2,x3  …. xn

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

3)  Скобок

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

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

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

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

А =

Список: <x1, x2,x3, x4 >

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

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

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

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

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

л

л

л

и

и

л

и

л

л

и

л

и

л

и

л

и

л

и

и

л

и

и

л

л

и

л

и

и

л

и

и

л

и

л

и

и

л

и

л

л

л

л

и

и

л

и

и

и

и

и

и

и

л

и

л

и

А: <xi1, xi2, xi3 … xik>

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

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

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

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

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

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

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

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

Похожие материалы

Информация о работе

Предмет:
Математика
Тип:
Конспекты лекций
Размер файла:
4 Mb
Скачали:
0