Математическая логика и теория алгоритмов. Стенюшкина В.А. - 6 стр.

ветствует основному из применяемых в математике правил вывода - Modus Po-
nens (Правило отделения).
       Эквиваленция – двухместная логическая операция ↔ («если и только
если…, то…») определяет высказывание А ↔ В («если и только если А, то В»),
которое считается истинным тогда и только тогда, когда А, В имеют одинако-
вые истинностные значения (оба истинны или оба ложны).
       Пример – «Квадратная матрица имеет обратную (А) если и только если
определитель матрицы отличен от нуля (В)». Это высказывание истинно , если
считать, что А, В истинны.
       Путем суперпозиции логических операций можно составлять все более
сложные высказывания. Порядок выполнения операций устанавливается с по-
мощью скобок и в соответствии с приоритетом операций:  , ∧, ∨, →, ↔ (в по-
рядке убывания).
       Пример – Пусть А, В – ложны, тогда высказывание (А∨В)∧(А∨В) ло-
жно.

      1.2 Булевы функции. Истинностные таблицы

       Булева функция – n-местная функция из {0,1}n в {0,1}. Каждой n-
местной логической операции α взаимно однозначно соответствует n-местная
булева функция yα=fα(x1,…,xn), x1,…,xn, y∈{0,1}, где двоичные переменные
x1,…,xn, y соответствуют высказываниям (операндам и результанту) и называю-
тся пропозициональными переменными. Другие названия булевых функций:
логические функции, функции истинности.
       Булеву функцию n переменных можно задать, таблицей истинности
(таблица 1.1):

      Таблица 1.1

       x1                 …                  xn                 f (x1,…,xn)
       0                  …                  0                  f (0,…,0)
       0                  …                  1                  f (0,…,1)
       …                  …                  …                  …
       1                  …                  1                  f (1,…,1)

      Каждый набор значений аргументов называется интерпретацией булевой
функции, а ее соответствующее значение – истинностным значением.
      Если число переменных n, то число различных наборов значений аргу-
ментов равно 2n, а число различных булевых функций – 2 2
                                                         n



      Булевы функции одной переменной: yi=fi(x), i=0..3 (таблица 1.2).
      Булевы функции двух переменных: yi=fi(x1,x2), i=0..15. Приведём табли-
цы некоторых двухместных булевых функций (таблица 1.3).