Формула (булева функция) имеет минимальную ДНФ, если она содержит наименьшее количество литералов среди всех ДНФ, эквивалентных ей.
Пример:
ДНФ - 
содержит 4 литерала, но она не является минимальной. Преобразуем ее ( ) =1* = . Получили один литерал.
Рассмотрим алгоритм Квайна Мак-Клоски:
Пусть функция задана СДНФ и 
, 
- два элементарных произведения, входящих в СДНФ. Пусть х - литерал, такой, что =xk и = 
k. Тогда 
= хk k = (x )k = k. Мы получили элементарное произведение, содержащее на один литерал меньше.
Такая операция называется склейкой.
Пример:
Ф=pqr р 
r 
q r. Произведем склейку 1й и 2й, а так же 3й и 4й элементарных произведений.
Ф= pr(q ) (q ) r 
pr r.
Решение логических задач.
В ряде задач приводится несколько высказываний относительно некоторого события, и имеются некоторые сведения об их ложности или истинности. Требуется определить какое из событий имело место. Такие задачи называются логическими.
Задача:
В конкурсе участвовало 4 девушки: Оля, Нина, Марина и Тамара.
На вопрос о том, как распределились между ними места, были получены ответы:
Оля 1 - Нина-2,
Оля-2 - Тамара-3,
Марина-2 - Тамара-4.
Известно, что хотя бы одна высказывание в каждом ответе истинно. Как распределились места?
Решение:
Введем обозначения:
О 
Н 
; О Т 
; М Т 
.
Тогда КНФ: (О Н ) (О Т ) (М Т ) 1, т.к. Каждое из элементарных сумм истинно.
Преобразуем в ДНФ, раскрывая скобки:
(О 
Н ) (О М О Т Т М Т Т )
(т.к. О2 М 2 =0 и Т3Т4=0) 
(О Н ) (О Т Т М ) (раскрываем скобки)
О О Т О Т 
М Н О Т Н Т М
О Т М .
Получили О Т М 1.
Следовательно: Оля-1,Марина-2, Тамара-3, Нина-4.
Анализ рассуждений.
Рассуждение - это вывод, позволяющий из данных высказываний (называемых посылками) получить новое высказывание (заключение).
|
|
Рассуждение состоит из последовательности посылок и заключения, то есть на основании известных свойств некоторых посылок мы получаем новое свойство этого объекта - заключение.
Рассуждение считается правильным, если из истинных посылок не может следовать ложного заключения.
Так как каждая посылка- это высказывание, то оно может быть записано в виде формулы. Следовательно, рассуждение – это последовательность формул. Заключение тоже является формулой. Если 
, 
,…, 
-это последовательность посылок. а 
- заключение, то будем писать
, ,…, ├ 
, или 
. (1)
И будем говорить, что из посылок логически следует заключение.
Нас будет интересовать только форма рассуждения, а не конкретное содержимое каждого высказывания, и на основании анализа формы мы будем делать вывод о том, правильное или неправильное рассматриваемое рассуждение. Если рассуждение признается правильным, то все рассуждения, приведенные по этой формуле, правильны, независимо от того, к какой предметной области они относятся.
Теорема.Рассуждение (1) правильно тогда и только тогда, когда формула 
… 
– тавтология. (2)
Доказательство:
Достаточность:
Если (2) -это тавтология, то конъюнкция посылок не может быть равно 0, значит =1, следовательно, рассуждение правильно.
Необходимость:
Если (1) правильно, то из истинности посылок 
не может следовать ложного заключения . Это означает, что (2) не может обратиться в 0. Следовательно, (2) – тавтология.
Что и требовалось доказать.
Пример 1: пусть имеется рассуждение
1. Если многоугольник правильный, то в него можно вписать окружность.
|
|
2. Данный многоугольник правильный.
3. Следовательно, в него можно вписать окружность.
Введем обозначения:
р - многоугольник правильный.
q - в многоугольник можно вписать окружность.
Посылки: 
, р. Заключение – q.
Рассуждение принимает вид: 
, р ├ q.
Формула, соответствующая этому рассуждению:
() .
Установим вид этой формулы. Сняв импликацию, получим:
(по законам де Моргана) 
(снимая двойное отрицание)
(по второму закону дистрибутивности)
. Это КНФ. Каждая элементарная сумма содержит высказывание со своим отрицанием, значит формула – тавтология.
Следовательно, рассуждение правильное.
Рассуждения, построенные по формуле () , будут правильными. Эта формула является тавтологией и называется правилом заключения (ПЗ).
() (ПЗ).
Пример 2: пусть имеется рассуждение
1. Если многоугольник правильный, то в него можно вписать окружность.
2. В многоугольник нельзя вписать окружность.
3. Следовательно, он неправильный.
Используя обозначения предыдущего примера, получим формулу, соответствующую этому рассуждению: () .
Аналогично предыдущему установим, что эта формула - тавтология, значит рассуждение правильное.
Данная формула называется правилом отрицания (ПО).
() 
(ПО).
Пример 3: пусть имеется рассуждение
Если многоугольник правильный, то в него можно вписать окружность, следовательно, если в многоугольник нельзя вписать окружность, то он неправильный.
Рассуждение ├ - правильное
Доказательство:
Соответствующая формула
() ( ) (
) 
р q (р q )(q ) 1, значит рассуждение правильное.
|
|
Данная формула называется правилом контрапозиции (ПК).
() ( ) (ПК).
Пример 4: пусть имеется рассуждение
Если в треугольнике все стороны равны, то он равносторонний.
Если треугольник равносторонний, то углы равны 60 
, следовательно, если в треугольнике стороны равны, то углы по 60 .
Введем обозначения:
р - в треугольнике стороны равны.
q – треугольник равносторонний.
r – углы равны 60 .
Рассуждение , q r ├ р r.
Соответствующая формула:
()(q r) (р r) 1 - рассуждение правильное.
Данная формула называется правилом силлогизма (ПС).
()(q r) (р r) (ПС).
Замечание. Полученные формулы называются правилами вывода.
Правило вывода иногда записывают в виде: 
.
ПЗ: 
, ПО: 
, ПК: 
,
ПС: 
.
Другие правила вывода:
· 
- введение дизъюнкции (ВД).
Доказательство. р (р q) р q 1.
· 
- удаление конъюнкции (УК).
Доказательство. рq р 
р р 1.
· 
- введение конъюнкции. (ВК)
Доказательство. рq рq 1
· 
удаление дизъюнкции (УД).
Доказательство.
Существуют и другие правила вывода
Замечание:
Так как правила вывода являются тавтологиями, то подстановка вместо элементарного высказывания любой формулы даст нам тавтологию, каждая из которых может быть объявлена правилом вывода.
Вывод.
Вывод- это последовательность формул, каждая из которых является посылкой или получена из предыдущих формул на основе правил вывода. Последняя формула есть заключение.
Пример: пусть имеется рассуждение
1. Если прямая не имеет общих точек с плоскостью, то она параллельна этой плоскости.
2. Если прямая имеет две общих точки с плоскостью, то она принадлежит этой плоскости.
3. Прямая не параллельна плоскости и не принадлежит ей, следовательно, она имеет одну общую точку и пересекает плоскость.
Введем обозначения:
х – прямая не имеет общих точек с плоскостью.
у – прямая параллельна плоскости.
z – прямая имеет две общих точки с плоскостью.
u – прямая принадлежит плоскости.
Рассуждение имеет вид: х у, z u, 
├ 
.
Построим вывод.
1) 
- посылка.
2) 
- УК (из 1);
3) 
- УК (из 1);
4) х у – посылка;
5) 
- ПО (из 4 и 2);
6) z u – посылка;
7) 
- ПО (из 6 и 3);
8) 
- ВК (из 5 и 7).
Теорема дедукции.
Теорема. Пусть дано , ,…, ├ (1), где - посылки.
Тогда , ,…, 
├ (2).
Доказательство:
Так как рассуждение (1) правильное, то из истинности посылок не может следовать ложного заключения. Предположим, что рассуждение (2) неправильное. Тогда из истинности посылок , ,…, следует ложное заключение, то есть 0. Но 1, значит 0. Но тогда рассуждение (1) неверно. А этого не может быть, Мы получили противоречие, значит предположение о неверности рассуждения (2) неверно.
Что и требовалось доказать.
Пример 1:
Рассмотрим ПО: р q, ├
По теореме дедукции р ├ ; (ПК).
Пример 2
Рассмотрим рассуждение. рr q ├ р .
По теореме дедукции: рr q, р ├ . Построим вывод:
1) р - посылка;
2) р – УК (1);
3) - УК (1);
4) р r q – посылка;
5) 
- ПО (4,3), т.е. ;
6) - УД (5,2).
Формула 
называется правилом расширенной контрапозиции (ПРК).
Предикаты.
При анализе рассуждений в логике высказываний нас не интересовала внутренняя структура самих высказываний. И это обстоятельство не позволяет анализировать большое количество рассуждений.
Например:
Через две данных точки проходит единственная прямая.
Точка лежит между двумя точками.
х>5.
Эти предложения не являются высказываниями, но становятся таковыми, если предметным переменным, входящим в эти предложения, задать конкретны значения. Так в последнем примере при х = 3 получим ложное высказывание, а при х = 8 истинное высказывание. Значения предметных переменных берутся из некоторого предметного множества А (точек, углов, прямых, чисел, ромбов и т.д.).
Введем понятие предиката.
Под предикатом предметной переменной х 
А будем понимать функцию Р(х) на {0,1}. Предикат р (х) называется одноместным предикатом
Например:
Предикат х > 5, x R: при х = 4 предикат обращается в ложное высказывание. При х = 7 предикат обращается в истинное высказывание.
Функция Р (х, у), где х, у А, принимающая значения во множестве {0,1} называется двухместным предикатом.
Например: х<у
Пусть У = 5, получим х < 5 – одноместный предикат. Если положить х = 4, то 4 < 5 – нульместные предикаты (высказывания).
Местность предиката - количество предметных переменных. Задание конкретного значения предметным переменным понижает местность предиката. Одноместные предикаты выражают свойство быть чем-то.
Например:
Свойство быть точкой. х – точка. Введем обозначение этого предиката: Т (х). Тогда Т (А) читается как А-точка.
Двухместные предикаты и предикаты более высокой местности выражают отношения между объектами.
Например: Двухместный предикат принадлежности – х у.
Если х – точка, а у – прямая, то читаем: точка х принадлежит прямой у.
Выбор предикатного символа остается за пользователем. Так, вместо х у можно ввести предикат Р (х, у), оговорив, что Р (,) – это предикат принадлежности (запятая в скобках свидетельствует о том, что предикат двухместный). Разумеется, что нельзя использовать одно и тоже обозначение для разных предикатов. Широко используются известные из математики обозначения предикатов ≈, ≠, ≡, ≤, ≥, ┴, ║, = Область истинности.
Пусть на множестве U задан предикат Р (х). Задавая х различные значения, мы будем получать высказывания, часть из которых истинна, а часть возможно ложна. Множество М 
(х) значений х, при которых предикат Р - истина, называется областью истинности.