Реферат 1. Канонические формы логических формул
 Скачать 24.36 Kb.
|
|
Тема реферата: «Канонические формы логических формул» Всякая логическая формула определяет некоторую булевую функцию. С другой стороны, для всякой булевой функции можно записать бесконечно много формул, ее представляющих. Одна из основных задач алгебры логики — нахождение канонических форм (т. е. формул, построенных по определенному правилу, канону), а также наиболее простых формул, представляющих булевы функции. Если логическая функция выражена через дизъюнкцию, конъюнкцию и отрицание переменных, то такая форма представления называется нормальной. Среди нормальных форм выделяют такие, в которых функции записываются единственным образом. Их называют совершенными. Особую роль в алгебре логики играют классы дизъюнктивных и конъюнктивных совершенных нормальных форм. В их основе лежат понятия элементарной дизъюнкции и элементарной конъюнкции. Формулу называют элементарной конъюнкцией, если она является конъюнкцией одной или нескольких переменных, взятых с отрицанием или без отрицания. Одну переменную или ее отрицание считают одночленной элементарной конъюнкцией. Формула называется элементарной дизъюнкцией, если она является дизъюнкцией (быть может, одночленной) переменных и отрицаний переменных. ДНФ И СДНФ Формула называется дизъюнктивной нормальной формой (ДНФ), если она является дизъюнкцией неповторяющихся элементарных конъюнкций. ДНФ записываются в виде: А1 v А2 v ... v Аn , где каждое Аn — элементарная конъюнкция. Формула А от k переменных называется совершенной дизъюнктивной нормальной формой (СДНФ), если: 1.А является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция k переменных х1, х2, …, xk, причем на i-м месте этой конъюнкции стоит либо переменная хi либо ее отрицание; 2. Все элементарные конъюнкции в такой ДНФ попарно различны. Например: А = х1 & НЕ х2 v х1 & х2 Совершенная дизъюнктивная нормальная форма представляет собой формулу, построенную по строго определенным правилам с точностью до порядка следования элементарных конъюнкций (дизъюнктивных членов) в ней. Она является примером однозначного представления булевой функции в виде формульной (алгебраической) записи. Теорема о СДНФ Пусть f(x1 х2, …, хn) – булева функция от n переменных, не равная тождественно нулю. Тогда существует совершенная дизъюнктивная нормальная форма, выражающая функцию f. Алгоритм построения СДНФ по таблице истинности: 1. В таблице истинности отмечаем наборы переменных, на которых значение функции f = 1. 2. Записываем для каждого отмеченного набора конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае – ее отрицание. 3.Все полученные конъюнкции связываем операциями дизъюнкции. КНФ И СКНФ Формула называется конъюнктивной нормальной формой (КНФ), если она является конъюнкцией неповторяющихся элементарных дизъюнкций. КНФ записываются в виде: А1 & А2 & ... & Аn , где каждое Аn – элементарная дизъюнкция. Формула А от k переменных называется совершенной конъюнктивной нормальной формой (СКНФ), если: 1. А является КНФ, в которой каждая элементарная дизъюнкция есть дизъюнкция k переменных x1, х2, …, хk, причем на i-м месте этой дизъюнкции стоит либо переменная xi, либо ее отрицание; 2. Все элементарные дизъюнкции в такой КНФ попарно различны. Например: А = (х1 v НЕ х2) & (х1 v х2) Теорема о СКНФ Пусть f(x1 х2, …, хn) – булева функция от n переменных, не равная тождественно нулю. Тогда существует совершенная конъюнктивная нормальная форма, выражающая функцию f. Алгоритм построения СКНФ по таблице истинности: 1. В таблице истинности отмечаем наборы переменных, на которых значение функции f = 0. 2. Записываем для каждого отмеченного набора дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 0, то в дизъюнкцию включаем саму переменную, в противном случае – ее отрицание. 3. Все полученные дизъюнкции связываем операциями конъюнкции. Из алгоритмов построения СДНФ и СКНФ следует, что если на большей части наборов значений переменных функция равна 0, то для получения ее формулы проще построить СДНФ, в противном случае – СКНФ. Пример Построить формулу для функции f(x1, х2, х3), заданной таблицей истинности:
Решение На большей части наборов значений переменных функция равна 0, поэтому проще построить СДНФ
F(x1,х2,х3) = x1 & х2 & х3 v x1 & х2 & х3 v x1 & х2 & х3. |