Функции алгебры логики

    Значение алгебры логики полностью зависит от значений входящих в эту формулу высказываний. По-этому формула алгебры логики является функцией входящих в нее элементарных высказываний.
    Например, формула \(( x \wedge y) \rightarrow \bar{z}\) является функцией трех переменных \(f ( x, y, z)\). Особенностью этой функции является то обстоятельство, что ее аргументы принимают одно из двух значений: ноль или единицу, и при этом функция также принимает одно из двух значений: ноль или единицу.
    Функцией алгебры логики \(n\) переменных (или функцией Буля) называется функция \(n\) переменных, где каждая переменная принимает два значения: 0 и 1, при этом функция может принимать только одно из двух значений: 0 или 1.
    Ясно, что тождественно истинные и тождественно ложные формулы алгебры логики представляют собой постоянные функции, а две равносильные формулы выражают одну и ту же функцию.
    Выясним, каково число функций \(n\) переменных. Очевидно, каждую функцию алгебры логики (как и формулу алгебры логики) можно задать с помощью таблицы истинности, которая будет содержать \(n\) строк. Следовательно, каждая функция \(n\) переменных принимает \(2^{n}\) значений, состоящих из нулей и единиц. Таким образом, функция \(n\) переменных полностью определяется набором значений из нулей и единиц длины \(2^{n}\). Общее же число наборов, состоящих из нулей и единиц, длины \(2^{n}\) равно \(2^{2n}\). Значит, число различных функций алгебры логики \(n\) переменных равно \(2^{2n}\).
    В частности, различных функций одной переменной четыре, а различных функций двух переменных шестнадцать. Выпишем все функции алгебры логики одной и двух переменных.
    Рассмотрим таблицу истинности для различных функций одной переменной. Она, очевидно, имеет вид:

х \(f_{1}(x)\)\(f_{2}(x)\)\(f_{3}(x)\)\(f_{4}(x)\)
1
1
1
0
0
0
1
0
1
0

    Из этой таблицы следует, что две функции одной переменной будут постоянными: \(f_{1}(x) \equiv 1\), \(f_{4}(x) \equiv 0\), а \(f_{2}(x) \equiv x\), и \(f_{3}(x) \equiv \bar{x }\).

    Таблица истинности для всевозможных функций двух переменных \(f_{i} \equiv f _{i} ( x, y)\) имеет вид:

х y\(f_{1}\)\(f_{2}\)\(f_{3}\)\(f_{4}\) \(f_{5}\)\(f_{6}\)\(f_{7}\)\(f_{8}\)\(f_{9}\)\(f_{10}\)\(f_{11}\)\(f_{12}\)\(f_{13}\)\(f_{14}\)\(f_{15}\)\(f_{16}\)
1 11111 011000100010
1 01110 110011000100
0 11101 100110101000
0 01011 101101010000

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

    \(f_{1} \equiv 1 ,\)     \(f_{5} \equiv \overline{x\wedge y } ,\)     \(f _{9} \equiv \overline{x \leftrightarrow y}\),      \(f _{13} \equiv \overline{y \rightarrow x}\),

    \(f _{2} \equiv x \vee y\),     \(f _{6} \equiv x\),     \(f _{10} \equiv \bar{y}\),     \(f _{14} \equiv \overline {x \rightarrow y} \),

    \(f _{3} \equiv y \rightarrow x\),     \(f _{7} \equiv x \leftrightarrow y\),     \(f _{11} \equiv y\),     \(f _{15} \equiv x \wedge y\),

    \(f _{4} \equiv x \rightarrow y\),     \(f _{8} \equiv \bar{x}\),     \(f _{12} \equiv \overline{ x \vee y} \),     \(f _{16} \equiv 0\).


2012-11-03 • Просмотров [ 1385 ]