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

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

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

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

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

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

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

СДНФ=;

СКНФ=

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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