В дальнейшем простые высказывания обозначаются буквами А, В, С, D, … и называются пропозициональными переменными.

В) Простые и составные высказывания. Логические связки.

Объектом и средством исследования в математической логике является теория множеств.

Правленная на наиболее удобные для анализа математические рассуждения.

А) Предмет математической логики.

Элементы математической логики

РАЗДЕЛ 1. Элементы математической логики и теории множеств

I семестр

 

 

Конспект лекций для студентов физико-технического факультета

 

Харьков-2005

 

 

Литература

1. Зорич «Математический анализ» 1, 2 том.

2. Фихтенгольц «Курс дифференциального и интегрального исчисления» 1, 2, 3 том.

3. Кудрявцев «Математический анализ» 1, 2, 3 том.

4. Демидович «Сборник задач и упражнений по математическому анализу».

 

 

 

Логика– анализ методов рассуждения, показывающий как надо рассуждать, для

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

Математическая логика – логика использующая математические методы и на-

 

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

2 ´2 = 4 – истинное высказывание. 2 ´2 = 5 – ложное высказывание.

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

Содержательно оправдано использование 5^ти логических связок, которые указываются в порядке приоритета:

1°– унарная (одноместная) – отрицание « Ø » (Ø А) (не А);

и бинарные:

2°– конъюнкция « Ù » (А Ù В, А и В);

3°– дизъюнкция « Ú » (А Ú В, А или В);

4°– импликация « Þ » (А Þ В, если А то В);

5°– эквиваленция « Û » (А Û В, А эквивалентно В).

Результаты применения этих операций к высказываниям приведены в следующих таблицах (таблицах истинности):

А	В	Ø А	А Ù В	А Ú В	А Þ В	А Û В

 

Здесь, и в дальнейшем, для простоты: истина – « 1 »; ложь – « 0 ».

 

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

Если ввести функцию f на высказываниях такую, что f (истина) = 1; f (ложь) = 0 то:

f (ØA) = 1 – f (A); f (В Ú А) = f (A) + f (A) – f (A)×f (В);

f (А Ù В) = f (A)× f (В); f (В Þ А) = 1 – f (A) + f (A) + f (A)× f (В),

f (AÛB) = 1 – f (A) – f (B) +2 f (A)f (B).

При этом исчисление высказывания производится с помощью арифметических действий над 0 и 1.

 

* Дополнительные логические связки:

« | » – антиконъюнкция (штрих Шефера); А | В Û Ø (А Ù В);

« ¯ » – антидизъюнкция (стрелка Пирса). А ¯ В Û Ø (А Ú В).

* Взаимосвязь логических связок:

Любую логическую связку можно выразить через три основные логические связки Ø , Ù , Ú:

(А Þ В) Û (Ø А Ú В);

(А Û В) Û (А Þ В) Ù (В Þ А) Û (Ø А Ú В) Ù (Ø В Ú А).

Законы де Моргана:

Ø (А Ù В) Û Ø А Ú Ø В;

Ø (А Ú В) Û Ø А Ù Ø В.

*Алгебраические свойства связок:

1°Коммутативны все бинарные связки, кроме импликации;

2°Ассоциативны Ù, Ú; неассоциативны Þ, Û;

3°Транзитивны Þ, Û;

4°Закон отрицания отрицания: Ø Ø А Û А;

5°Принцип тождества: Ø А Ú А Û «и», Ø А Ù А Û «л»;

5°Правила поглощения: А Ú (А Ù В) Û А, А Ù (А Ú В) Û А.

 

С). Формулы и их классификация.

Def: Формула :: = {пропозициональная переменная | Ø U | (U Ù V) | (U Þ V) | (U Û V)}, где U и V –формулы.

Формула:

а) выполнима – если существует ($) набор параметров, при которых формула истинна;

б) тождественно-истинная или тавтология – если для любого (") набора параметров формула истинна;

в) опровержима – если существует ($) набор параметров, при которых формула ложна;

г) тождественно-ложная или противоречие – если для любого (") набора параметров формула ложна.

Формула называется формулой с тесными отрицаниями, если в ней нет связок Þ и Û, и отрицания относятся только к пропозициональным переменным.

Произвольная конъюнкция (дизъюнкция) формул, каждая из которых есть пропозиционная переменная или ее отрицание называется элементарной конъюнкцией (дизъюнкцией).

Def: Произвольная дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой, а произвольная конъюнкция элементарных дизъюнкций называется конъюнктивной нормальной формой (Д.Н.Ф. и К.н.ф.).

Def: Д.н.ф. называется совершенной (с.д.Н.Ф.), если каждая переменная формулы входит в элементарную конъюнкцию ровно один раз – с отрицанием или без него.

Def: К.н.ф. называется совершенной (с.к.Н.Ф.), если каждая переменная формулы входит в элементарную дизъюнкцию ровно один раз – с отрицанием или без него.

 

Пример: Исчислить высказывание: ((А Þ В) Þ (Ø (С Ú А) Þ В)).

1 5 3 2 4

Внизу указан порядок операций.

 

1) Таблицы истинности:

А	В	С

В 5^ом столбце указана истинность всего составного высказывания при различных значениях истинности А, В и С.

2) С помощью формулы: (А Þ В) Û (Ø А Ú В) избавимся от импликаций:

(Ø А Ú В) Þ (С Ú А Ú В)

Ø (Ø А Ú В) Ú С Ú А Ú В и применим один из законов де Моргана.

(А Ù ØВ) Ú С Ú А Ú В - получена формула с «тесными» отрицаниями.

Запишем последнюю формулу в виде:

* (А Ù ØВ) Ú (С)Ú (А)Ú (В), трактуя каждую скобку как элементарную конъюнкцию, видим: дизъюнкцию элементарных конъюнкций, т.е. Д. Н.Ф. она не является совершенной т.к. в каждую скобку входят не все переменные формулы.

Запишем последнюю формулу в виде:

(А Ù ØВ) Ú (С Ú А Ú В) и применим дистрибутивный закон

(А Ú С Ú А Ú В) Ù (ØВ Ú С Ú А Ú В),

(А Ú С Ú В) Ù (ØВ Ú С Ú А Ú В), здесь последняя скобка есть тавтология, поэтому получаем: (А Ú В Ú С) и, трактуя скобку как элементарную дизъюнкцию, делаем заключение, что перед нами К.Н.Ф., причем С.К.Н.Ф. т.к. в элементарную дизъюнкцию входят все три переменные.

 

Примечание: С.К.Н.Ф. позволяет сказать, что исходная формула ложна только в одном случае, если А, В, С – ложны. Зная С.К.Н.Ф. , легко написать и С.Д.Н.Ф если учесть, что отдельные элементарные конъюнкции описывают случаи истинности формы.

( (А Ú В Ú С) Û (ØА Ù В Ù С) Ú (А Ù ØВ Ù С) Ú (А Ù В Ù ØС) Ú

(ØА Ù ØВ Ù С) Ú (ØА Ù В Ù ØС) Ú (А Ù ØВ ÙØ С) Ú (ØА Ù ØВ Ù ØС)) .

В записанной формуле слева от Û стоит С.К.Н.Ф. а справа С.Д.Н.Ф .

· Исчислить высказывание можно также, если смоделировать исходное составное высказывание эквивалентной электрической схемой.

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

При этом: конъюнкция А Ù В может быть промоделирована последовательным включением в цепь двух выключателей А и В, а дизъюнкция А Ú В - параллельным.