close

Вход

Забыли?

вход по аккаунту

?

9

код для вставкиСкачать
Билет № 9
Функции алгебры логики. Представление произвольной функции алгебры логики в виде формулы алгебры логики.
Функции алгебры логики. Значение формулы алгебры логики полностью определяется значениями входящих в нее переменных, поэтому любая формула алгебры логики является функцией входящих в нее элементарных высказываний.
x v y -> z = f(x, y, z)
Функцией алгебры логики n - переменных (функцией Буля) называется функция, в которой каждая переменная принимает значения из множества (0, 1) и сама функция принимает значения из этого множества.
Тождественно истинные и логические формулы представляют собой постоянные функции, а две равносильные формулы определяют одну и ту же функцию.
Каждую функцию можно задать с помощью таблицы истинности, которая может иметь 2n строк => функция n - переменных полностью определяется набором.
(22)n - общее число наборов из 0 и 1 => таково количество функций.
При n =1 существует 4 различных функции.
XF1F2F3F41110001010
F1 = 1, F2 = x, F3 = ¬x, F4 = 0
Если n = 2, то функций будет 16.
Представление произвольной функции алгебры логики в виде формулы алгебры логики
Пусть дана F ( x1, x2, ...,xn)
F (1, 1, ...,1) & x1&x2&...&xn v F (1, 1,..., 1, 0)&x1 & x2&...&xn-1 & ¬xn v F (1, 1, ...1, 0, 1) &x1 & x2 & x3...&xn-2 & ¬xn-1& xn v...v F (0, 0, ...,0) & ¬x1 & ¬x2&...& ¬xn (*)
Рассмотрим эту формулу, которая получена следующим образом: каждое слагаемое данной логической суммы представляет собой конъюнкцию, первым членом которой является значение функции F при определенном наборе переменных, а остальные члены конъюнкции, либо переменные, либо их отрицание. Причем под отрицанием находятся те же переменные, которые равны в первом члене конъюнкции. Покажем, что формула (*) полностью определяет исходную функцию F. Для этого надо показать, что значение функции F и формулы (*) совпадают на всех значениях переменных. Пусть x1=0, а остальные 1, тогда F (0, 1, 1, ..., 1) и при этом логическое значение слагаемого F (0, 1, 1, ..., 1) & ¬x1 &x2&...&xn будет равно F (0, 1, 1, ..., 1).
Все остальные логические слагаемые формулы (*) равны 0 потому что в конъюнкции x1 равен 0.
Вид формулы (*) можно упростить:
1) Можно отбросить те слагаемые, в которых член конъюнкции равен нулю;
2) Если в логическом слагаемом первый член конъюнкции равен нулю, то вся конъюнкция равна нулю;
3) Если первый член конъюнкции равен 1, то этот член можно не записывать
В результате получится формула, которая содержит только переменные высказывания и их отрицание и будет обладать четырьмя свойствами:
1) Каждая логическая слагаемая формулы будет содержать все переменные, входящие в функцию F
2) Все логические слагаемые формулы будут различны;
3) Ни одно логическое слагаемое не будет содержать одновременно переменную и её отрицание;
4) Ни одно логическое слагаемое не будет содержать одну и ту же переменную дважды.
Из приведенных только что рассуждений следует, что каждой не тождественно ложной функции соответствует единственная форма рассматриваемого виду.
Если функция n-переменных задана таблицей истинности, то соответствующая формула алгебры логики может быть получена следующим образом:
Для каждого набора значений, на которых функция принимает значение 1, записывается конъюнкция элементарных высказываний, причем если значения высказываний равны 1, то записывается оно само (высказывание), а если 0, то записывается отрицание этого высказывания. Если значение функции равно 0, то и вся конъюнкция равна 0, следовательно, эту строку можно из рассмотрения исключить. Дизъюнкция всех построенных таким образом конъюнкций даст конечный результат. Пример:
x y zF(x, y, z)x&y&¬z v x&¬y&z v ... v ¬x&¬y&¬z
1 1 1 0
1 1 0 1
1 0 1 1
1 0 0 0
0 1 1 0
0 1 0 1
0 0 1 0
0 0 0 1
Автор
lovematanfo
Документ
Категория
Без категории
Просмотров
159
Размер файла
18 Кб
Теги
билет
1/--страниц
Пожаловаться на содержимое документа