Шпаргалка «Экзаменационная» по Математической логике (Дьячков А. М.)

Кирилл Николоев сб, 19.03.2016 15:50

1.Алгебра высказываний; пропозициональные связки и формы, истинностные таблицы Высказывание – повествовательное предложение, о котором можно сказать, истинно оно или ложно. Значение «истинно» и «ложно» обычно обозначаются 1 или 0, или И и Л.

Содержательно логические операции обычно интерпретируют следующим образом: отрицание (инверсия) (− ) − «не» дизъюнкция − «или» конъюнкция & (А&B или A.В) − «и» импликация → − «если … , то» эквивалентность ~ − «тогда и только тогда» (или «эквивалентно»)

приоритеты по выполнению действий: , &, , →, ~ . Символы , &, , →, ~ наз-ся пропозициональными(или логическими) связками. Буквы, обозначающие высказывания, наз-ся пропозициональными буквами. Осмысленные формулы, составленные из пропозициональных букв, пропозициональных связок, а также скобок, указывающих порядок выполнения операций, наз-ся пропозициональными формами(ПФ).

Операции логики высказываний можно задать с помощью табл.: А В А А В А&B A→B A~B 0 0 I 0 0 I I 0 I I I 0 I 0

I 0 0 I 0 0 0 I I 0 I I I I Используя эту таблицу можно получить истинностную таблицу для произвольной ПФ. 2.Алгебра высказываний; тавтологии и противоречия

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

1) Если А – тавтология, то А – противоречие. И наоборот. 2) Если А и А→В – тавтологии, то В – тавтология. 3) Если А→В и А→В – тавтологии, то А – противоречие. 4) Если в тавтологии вместо пропозициональных букв подставить произвольные ПФ, то снова получится тавтология.

3.Алгебра высказываний; логическая эквивалентность и логическое следствие Логическая равнозначность: ЭКВИВАЛЕНТНОСТЬ - определяет результат сравнения двух простых логических выражений А и В. Результатом ЭКВИВАЛЕНТНОСТИ является новое логическое выражение, которое будет истинным тогда и только тогда, когда оба исходных выражения одновременно истинны или ложны. Обозначается символом эквивалентности ~.

Логическое следование: ИМПЛИКАЦИЯ - связывает два простых логических выражения, из которых первое является условием (А), а второе (В)– следствием из этого условия. Результатом ИМПЛИКАЦИИ является ЛОЖЬ только тогда, когда условие А истинно, а следствие В ложно. Обозначается символом следовательно → и выражается словами ЕСЛИ … , ТО …

4. Алгебра высказываний; дизъюнктивная и конъюнктивная нормальные формы Дизъюнктивной нормальной формой(ДНФ) наз-ся дизъюнкция элементарных конъюнкций. При этом допускается, что может быть всего одно дизъюнктивное слагаемое.

Теорема. Всякая истинностная функция F порождается некоторой ДНФ Конъюнктивной нормальной формой(КНФ) наз-ся конъюнкция элементраных дизъюнкций. При этом допускается, что может быть всего один конъюнктивный сомножитель.

Теорема. Всякая истинностная функция F порождается некоторой КНФ. 5. Алгебра высказываний; полные системы функций, базис Система пропозициональных связок наз-ся полной, если любая пропозициональная форма может быть записана с помощью связок только из этой системы. Сис-ма пропозициональных связок наз-ся независимой, если никакая из связок этой сис-мы не может быть выражена через другие связки той же сис-мы. Полная независимая сис-ма связок наз-ся базисом.

Сис-ма связок {, ,&} явл-ся полной. Теорема. Система связок {, } явл-ся базисом 6. Понятие формальной аксиоматической теории. (ФАТ) Формальные аксиоматические теории (ФАТ) представляют собой одно из средств, используемых для решения более сложных вопросов логики, для решения которых нет эффективной процедуры. Задать ФАТ – значит определить следующие ее компоненты:

1)Алфавит теории-счетное множ-во, элементы которого служат символы для построения слов. 2) Формулы теории – те слова, которые считаются осмысленными. 3) Аксиомы теории – те формулы, которые счит-ся не нуждающимися в док-ве. Множ-во аксиом может быть бесконечным.

4) Правила вывода, определяющие, в каком случае мы считаем одну формулу непосредственным следствием других. Если для формулы A сущ-ет вывод,то говорят, что она явл-ся теоремой ФАТ, и пишут так: . 7. Исчисление высказываний, как формальная аксиоматическая теория (ФАТ).

В кач-ве основного примера ФАТ рассмотрим исчисление высказываний (ИВ). 1)Алфавит ИВ состоит из пропозициональных букв, пропорциональных связок и –(не) и скобок. 2) Формулы ИВ – это все ПФ, содержащие лишь связки –(не) и

Скачать файлы

Похожие документы