Простая конъюнктивная нормальная форма

Простой конъюнктивной нормальной формой (ПКНФ) некоторой формулы А является равносильная ей формула А’, представляю­щая собой конъюнкцию элементарных дизъюнкций. Элементар­ной называется дизъюнкция, в состав которой входят или переменные, или их отрицания. Из табличных определений отрицания и слабой дизъюнкции можно вывести следующее положение: элементарная дизъюнкция будет всегда истинной, если в ней содержится хотя бы одна пара дизъюнктов, один из которых является переменной, а второй — ее отрицанием. Из табличного определения конъюнкции можно сделать вывод, что если каждый конъюнкт является истинной дизъюнкцией, то вся формула будет истинной. Совершенная конъюнктивная нормальная форма  Всякая не всегда истинная формула может быть приведена к совер­шенной конъюнктивной нормальной форме позволяет не только упростить исходную формулу, но и решить за­дачу отыскания всех ее логических следствий или всех следствий из любого числа исходных утверждений, таким образом, дает возможность обзора тех следствий из формулы которые сами имеют Для выявления про­стых следствий из формулы ее необходимо привести к Простым следствием называется такое, которое не поглощается, согласно равносильности [12], никаким другим следствием тако­го же вида. Сокращенной конъюнктивной нормальной формой некоторой формулы является ее КНФ, соответствующая следую­щим условиям: ни в одном конъюнктивном члене нет одинаковых дизъюнктов; ни в одном конъюнктивном члене нет таких дизъюнктов, один из которых — переменная, а другой — ее отрицание; если в формуле есть такие два конъюнктивных члена, в од­ном из которых содержится некоторая переменная, а во втором — ее отрицание, и если для других членов это не характерно, то в ней должен быть конъюнктивный член, содержащий все переменные этой пары, за исключением той переменной, о которой идет речь. которая является совершенной дизъюнктивной нормальной фор­мой формулы (а), а ее дизъюнктивные члены — гипотезами фор­мулы (а). Присоединив формулу (а) к любому из дизъюнктов формулы (г) знаком импликации, образуем тождественно-истин­ную формулу. Таким образом, с помощью СвДНФ можно полу­чить обзор всех гипотез некоторой формулы.

Комментарии запрещены.