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

Кирилл Николоев сб, 19.03.2016 19:58

1.Алгебра высказываний, пропозициональные связи и формы, истинностные таблицы. Высказывания – повествовательное предложение, ктр можно приписать истинностное значение. Сокращенно истинностное значение «истина» обозначается цифрой 1 или буквой И, а «ложь» - цифрой 0 или буквой Л. Сами высказывания обозначаются латинскими буквами A, B, A1, A2…

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

Отрицание A высказывания A Конъюнкция A&B Дизъюнкция A v B Импликация A→ B Эквивалентность A≡B A B A A&B A v B A→ B A≡B 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1 Символы , &, v, → и ≡ называются пропозициональными (или логическими) связками. Буквы, обозначающие высказывания, называются пропозициональными буквами. Осмысленные формулы, составленные из пропозициональных букв, пропозициональных связок, а так же скобок, указывающих порядок выполнения операций, называются пропозициональными формами. Обозначаются ПФ прописными латинскими буквами.

Приоритет операций: , &, v, → и ≡ 2.Алгебра высказываний, тавтологии и противоречия. Все возможные комбинации истинностных значений пропозициональных букв в ПФ называются истинностными наборами. Если ПФ принимает значение 1 на любом истинностном наборе (тождественная «истина»), то эта ПФ называется тавтологией. Если же ПФ принимает значение 0 на любом истинностном наборе (тождественная «ложь»), то эта ПФ называется противоречием. Если ПФ не является противоречием, то она называется выполнимой. Из тавтологий получаются высказывания, истинные по форме, а из противоречий – ложные по форме (а не по содержанию). 3. Алгебра высказываний, логическое следствие и логическая эквивалентность.

Логическим следствием ПФ A называется такая ПФ B, что ПФ A→B является тавтологией. В этом случае говорят, что ПФ B логически следует из ,A или что A логически влечет B. Логически эквивалентными называются такие ПФ A и , что ПФ A≡B является тавтологией. Логическая эквивалентность ПФ в точности означает их совпадение как функций нескольких переменных, т.е. то, что на каждом истинностном наборе они принимают одинаковые значения. Логическая эквивалентность ПФ A и обозначается так: A ~B.

Эквивалентности: Коммутативность A v B~ B v A A&B~B&A Дистрибутивность (AvB)&C~(A&C)v(B&C) (A&B)vC~(AvC)&(BvC) Ассоциативность (AvC)vC~Av(BvC) (A&B)&C~A&(B&C) Закон двойного отрицания AA~A Законы де Моргана

(AvB)~ A&B (A&B)~ AvB Законы поглощения AvA~A A&A~A AvA~1 A&A~0 Av1~1 Av0~A A&1~A A&0~0 А так же эквивалентности: A→ B~AvB A→ B~(A&B) A≡B ~(A→B)&(B→A) A≡B ~(A&B)v(A&B) 4. Алгебра высказываний: дизъюнктивная и конъюнктивная нормальные формы.

Если A – пропозициональная буква A^σ {█(A,если σ=1@A,если σ=0)┤ Элементарной конъюнкцией называется ПФ следующего вида: A_1^(σ_1 )&A_2^(σ_2 )&…&A_n^(σ_n ) При этом допустимо, чтобы n=1, в этом случае элементарная конъюнкция – это либо A1, либо A1.

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций. При этом допускается, что может быть всего одно дизъюнктивное слагаемое. Дизъюнктивная нормальная форма, зависящая от пропозициональных букв A1,…,An, называется совершенной (СДНФ), если все дизъюнктивные слагаемые различны, и каждое из них имеет вид

A_1^(σ_1 )&A_2^(σ_2 )&…&A_n^(σ_n ) Элементарной дизъюнкцией называется ПФ следующего вида: A_1^(σ_1 ) vA_2^(σ_2 ) v…vA_n^(σ_n ) Конъюнктивной нормальной формой (КНФ) называется конъюнкция элементарных дизъюнкций. При этом допускается, что может быть всего один конъюнктивный сомножитель. 5.Алгебра высказываний: полные системы функций, базис.

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

6.Понятие формальной аксиоматической теории. Задать ФАТ – значит определить следующие ее компоненты: Алфавит теории – счетное множество, элементы которого служат символами для построения слов. Формулы теории – те слова, которые считаются осмысленными.

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

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