 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Основные логические функции
|
|
В алгебре логики логические формулы рассматриваются как алгебраические выражения, которые можно преобразовывать по определенным правилам, реализующим логические законы. Алгебра логики как раздел математической логики изучает строение сложных логических высказываний (логических формул) и способы установления их истинности с помощью алгебраических методов.
Основные объекты, изучаемые в этом разделе, - формулы алгебры логики, состоящие из букв, знаков логических операций и скобок. Буквы обозначают логические (двоичные) переменные, которые принимают только два значения -"ложь" и "истина". Знаки операций обозначают логические операции (логические связки). Каждая формула задает логическую функцию - функцию от логических переменных, которая сама может принимать только два логических значения.
Итак, пусть В = {0, 1} - бинарное множество, элементами которого являются формальные символы 1 и 0, не имеющие арифметического смысла и интерпретируемые как {"да", "нет"}, {"истинно", "ложно"} и т.д.
Алгебра логики - алгебра, образованная множеством В ={0, 1} вместе со всеми возможными операциями на нем.
Функцией алгебры логики (или логической функцией) f от п переменных f (х1, х2..., хn) называется п-арная логическая операция на В, т.е. f: Вn —> В. Множество всех логических функций (логических операций) обозначается Р2, множество всех логических операций п переменных - Р2 (п).
Любую логическую функцию f (х1, х2..., хn) можно задать таблицей истинности, в левой части которой выписаны все возможные наборы значений ее аргументов х1, х2..., хn,, а правая часть представляет собой столбец значений функций, соответствующих этим наборам. Набор значений переменных, на котором функция принимает значение f =1, называется единичным набором функции f; множество всех единичных наборов - единичным множеством функции f. Аналогично набор значений, на котором / = 0, называется нулевым набором функции f, а множество нулевых наборов - нулевым множеством.
Число всех возможных различающихся наборов значений п переменных логической функции f (х1, х2..., хn) равно 2n (равно числу всех возможных двоичных векторов длины п). Число всех различных функций п переменных равно числу возможных расстановок нулей и единиц в столбце с 2n строками, т.е. |Р2 (п)|= 22n.
Особую роль в алгебре логики играют логические функции одной и двух переменных - унарные и бинарные логические операции, так как очевидным образом интерпретируются естественными логическими связками "не", "и", "или" и т.д., широко используемыми при описании систем, явлений, формализации рассуждений и пр.
φ0 и φ3, - константы 0 и 1 соответственно. Значения этих функций не зависят от переменной х, в таких случаях говорят, что переменная х является несущественной (фиктивной) для этих функций;
φ1(х) =х (повторение переменной).
Таблица 3.1
| х | φ0 | φ1 | φ2 | φ3 |
Множество всех логических функций двух переменных Р2 (2) - бинарных логических операций - представлено в табл. 3.2 своими таблицами истинности; | Р2 (2)| = 16 функций, из которых шесть имеют фиктивные переменные.
Таблица 3.2
Дата публикования: 2015-03-26; Прочитано: 1070 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
