| Логической функцией называется функция f (x 1, x 1,...,x n), которая, так же как и ее аргументы, может принимать только два значения (0 и 1).
| | |
|
| Совокупность значений аргументов будем называть набором. Каждому набору присваивается номер N, равный двоичному числу, образованному значениями аргументов на этом наборе. Условимся, что младшему разряду этого числа соответствует значение аргумента со старшим индексом, и наоборот.
| |
|
| Итак:
| |
|
|
 ,
где n - общее число переменных.
| |
|
| Например, пусть логическая функция зависит от трех переменных f(x1,x2,x3). Тогда набор x1 =1, x2 =1, x3 =0 будет иметь номер
| |
|
|
 .
| |
|
| Любую логическую функцию можно задать таблицей истинности, в левой части которой вписаны все возможные наборы значений ее аргументов x1,x2,...,xn, а правая часть - столбец значений функции, соответствующих этим наборам:
| |
|
|
| № набора
| x1,x2,...,xn
| f(x1,x2,...,xn)
| |
| Набор значений аргументов
| Значение функции
(0 или 1)
| |
| | :
| | 2n - 1
| | |
|
| Число строк таблицы равно 2n (число всех возможных наборов из n аргументов). Число различных функций n переменных равно 2 в степени 2n - числу возможных расстановок нулей и единиц в столбце с 2n строками.
| |
|
| Пусть n = 1. Таблица f(x) содержит две строки, а самих функций - четыре.
| |
|
|
| № набора
| x
| f(x)
| | № набора
| x
| f(x)
| |
|
|
| |
|
|
| |
|
|
| |
|
|
|
|
Константа 0
f(x)=0
|
Повторение
f(x)=x
|
| № набора
| x
| f(x)
| | № набора
| x
| f(x)
| |
|
|
| |
|
|
| |
|
|
| |
|
|
|
Отрицание f(x)= 
| Константа1 f(x)=1
| | |
|
| Для n = 2 таких функций f(x1, x2) шестнадцать. Наиболее употребляемые из них:
| |
|
|
| № набopа
| x1
| x2
| f(x1, x2)
| | № набopа
| x1
| x2
| f(x1, x2)
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
|
Дизъюнкция
| Конъюнкция
| | |
|
|
| № набopа
| x1
| x2
| f(x1, x2)
| | № набopа
| x1
| x2
| f(x1, x2)
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
|
Штрих Шеффера
(" И - НЕ ")
|
Стрелка Пирса
(" ИЛИ - НЕ ")
| | |
|
|
| № набopа
| x1
| x2
| f(x1, x2)
| | № набopа
| x1
| x2
| f(x1, x2)
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
|
Импликация
| Эквивалентность (равнозначность)
 или x1 -> x2,
или x1  x2.
| | |
| | Числовой способ задания логической функции. Логическую функцию от n аргументов будем еще обозначать символом f n. Если к тому же известно, что она равна 1 на наборах с номерами a i, i = 0,1,...,2 n-1, то будем записывать это в виде:
| |
|
|
 .
| |
|
| Например, для функции "Штрих Шеффера"  .
| |
| 35.
| Если известно, что f n равна 0 на наборах с номерами b i, i = 0,1,...,2 n-1, то будем записывать это в виде:
| |
|
|
 .
| |
|
| Например, для " Стрелки Пирса "  .
| |
| 36.
| Аргументы (переменные) и булевы функции с определенными на них элементарными операциями "отрицание", "конъюнкция" и "дизъюнкция" образуют алгебру Буля (булеву алгебру).
| |
| 37.
| В этой алгебре справедливы следующие основные соотношения, тождества, правила и законы.
| |
|
|
| 0 · 0 = 0,
| 0  0 = 0,
| | | 0 · 1 = 0,
| 0 1 = 0,
| | | 1 · 0 = 0,
| 1 0 = 0,
|  ,
| | 1 · 1 = 1,
| 1 1 = 1,
|  .
| | |
|
|
| |
|
|
| x · 0 = 0,
| x 0 = 0
| | | x · 1 = 1,
| x 1 = 1
| |  ,
| 
| | | x · x ·...· x,
|  ,
|  .
| | |
|
|
| |
|
| а) правило де Моргана:
б) конъюнктивное поглощение (x 1 поглощает x 1 x 2):
в) дизъюнктивное поглощение (x 1 поглощает x 1 · x 2);
г) конъюнктивное склеивание по x 2:
д) дизъюнктивное склеивание по x 2:
 ;
е) конъюнктивное развертывание по x 2:
 ;
ж) дизъюнктивное развертывание по x 2:
 .
а) ассоциативность дизъюнкции и конъюнкции:
 ,
б) коммутативность дизъюнкции и конъюнкции:
в) дистрибутивность конъюнкции относительно дизъюнкции:
 ;
г) дистрибутивность дизъюнкции относительно конъюнкции:
 .
| |
