Логичечкие функции

     Логические  функции 

     Науку о формах и законах мышления называют логикой. Одним из направлений логики как науки является формальная логика, составной частью которой является математическая логика. Одним из важнейших  разделов математической логики является алгебра логики или булева алгебра (по имени английского математика и логика Джорджа Буля).

     Основным  понятием алгебры логики является понятие  высказывания. Высказыванием называется повествовательное предложение, о  котором можно сказать, что в  данный момент оно истинно или  ложно, но не то и другое одновременно. Например, высказывание «Луна – это спутник Земли» истинно, а высказывание «микропроцессор разработан в 1905г.» ложно. «Истинность» или «ложность» предложения есть истинностное значение высказывания.

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

     Каждому высказыванию ставят в соответствие переменную, равную «1», если высказывание истинно, и равную «0», если оно ложно. Таким образом, можно определить двухэлементное множество В и двоичные переменные, принимающие значения из В. Его элементы часто обозначают «0» и «1», однако они не являются числами в обычном смысле (хотя по некоторым свойствам и похожи на них). Наиболее распространенная интерпретация двоичных переменных – логическая: «да» – «нет», «истинно» (И) – «ложно» (Л). В контексте, содержащем одновременно двоичные и арифметические величины и функции, эта интерпретация обычно фиксируется явно: например, в языках программирования (Паскаль, Си и др.) вводится специальный тип переменной – логическая переменная, значения которой обозначаются «true» и «false». В дальнейшем изложении будем считать, что В = {0, 1}, рассматривая «0» и «1» как формальные символы, не имеющие арифметического смысла.

     Алгебра, образованная множеством В вместе со всеми возможными операциями на нем, называется алгеброй логики. Функцией алгебры логики (или логической функцией) от п переменных называется n-арная операция на В. Логическая функция f(x1,x2, ... ,xn) – это функция, принимающая значения «0», «1». Множество всех логических функций будем обозначать Р2, множество всех логических функций п переменных – P2(n).

     Алгебра, образованная k-элементным множеством вместе со всеми операциями на нем, называется алгеброй k-значной логики, а n-арные операции на k-элементном множестве называются k-значными логическими функциями п переменных; множество всех k-значных логических функций обозначается Pk .

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

     Наборы, на которых функция f = l, часто называют единичными наборами функции f, а множество единичных наборов – единичным множеством f. Соответственно наборы, на которых f = 0, называют нулевыми наборами f.

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