<<
>>

Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы

Рассмотрим произвольную -членную операцию , заданную своей таблицы значений, не являющуюся противоречием.

Рассмотрим строки таблицы, в которых принимает значения “И”. Для каждой строки составим элементарные конъюнкции из множителей, где -й множитель равен (в этой строке принимает значение “И”) или (в этой строке принимает значение “Л”). Далее возьмем дизъюнкцию всех полученных конъюнкций. В итоге получится формула (д. н. ф. ), задающая операцию, равносильную . Действительно, каждая из построенных конъюнкций будет истинна только при тех значениях истинности высказываний , которые стоят в соответствующей строчке. Поскольку была взята дизъюнкция по всем наборам значений истинности высказываний , на которых истинна, то построенное высказывание истинно на всех этих наборах и только на них. На остальных наборах оно ложно.

Построенная формула называется совершенной дизъюнктивной нормальной формой (СДНФ) операции .

Аналогично, рассматривая строки, в которых операция , не являющаяся тавтологией, принимает значения “Л”, и составляя конъюнкцию (число множителей равно числу отмеченных строк таблицы) дизъюнкций из слагаемых, где -е слагаемое равно (в этой строке принимает значение “Л”) или (в этой строке принимает значение “И”). В итоге получится формула, задающая операцию, равносильную . Построенная формула называется совершенной конъюнктивной нормальной формой (СКНФ) операции .

Пример. Построить СДНФ и СКНФ операции, заданной таблицей истинности.

И И И Л
И И Л И
И Л И Л
И Л Л И
Л И И Л
Л И Л Л
Л Л И Л
Л Л Л И

Решение. Операция принимает значение “И” только на трех наборах, а “Л” на пяти наборах.

Соответственно,

СДНФ=;

СКНФ=

.

Теорема 3. Любая логическая операция может быть выражена через операции отрицания и конъюнкции.

Доказательство. Выразим дизъюнкцию через операции отрицания и конъюнкции, используя закон двойного отрицания и закон де Моргана: .

Найдя СДНФ или СКНФ данной операции и заменив в них дизъюнкцию через операции отрицания и конъюнкции, получим формулу, содержащую только операции отрицания и конъюнкции. Теоремы

Теоремы в математике чаще всего формулируются в виде «», где – условие теоремы (то, что дано), а – заключение (то, что утверждается). и являются высказываниями (возможно, неопределенными).

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

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

Условие достаточно для , если верна импликация .

Теоремы и называются обратными друг другу. Первую называют прямой теоремой, другую – обратной.

Приведем пример.

Прямая теорема. Если треугольник прямоугольный, то сумма квадратов его катетов равна квадрату гипотенузы. Обратная теорема. Если в некотором треугольнике сумма квадратов двух сторон равна квадрату третьей стороны, то такой треугольник прямоугольный.

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

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

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

Теорема называется противоположной обратной теореме.

Противоположная теорема – это теорема, условие и заключение которой являются отрицаниями условия и заключения данной теоремы.

Например, теорема, противоположная теореме Пифагора, может быть сформулирована так: если треугольник не прямоугольный, то квадрат любой его стороны не равен сумме квадратов двух других сторон.

Метод доказательства от противного. Ранее было отмечено, что высказывания и равносильны. Поэтому иногда для доказательства теоремы предполагают истинным высказывание и пытаются вывести отсюда справедливость высказывания . Если это удается (т.е. будет доказана теорема ), то исходную теорему тоже можно будет считать доказанной.

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

<< | >>
Источник: Дискретная математика. Лекции. 2016

Еще по теме Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы:

  1. 2.1. Рабочая программа (объем дисциплины 150 часов)
  2. 3.3. Элементы алгебры логики
  3. Глава II. Классификация суждений
  4. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
  5. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
  6. 2.1.5.Совершенные нормальные формы
  7. 1.7. Формы представления высказываний