Алгебра логики высказываний Основные понятия
жүктеу/скачать 0.9 Mb.
|
- Бұл бет үшін навигация:
- Функции алгебры логики
Законы алгебры логикиВ логике высказываний известно много общезначимых формул, которые также называются законами логики высказываний. Основными законами являются следующие:
Доказательство этих и последующих законов элементарно осуществляется с помощью построения таблиц истинности или простейших логических рассуждений. Следующая группа законов представляет взаимосвязь между логическими операциями:
Замечательным следствием приведенных выше законов является следующий факт. Любую логическую формулу можно заменить равносильной ей, но содержащую только две логические операции: конъюнкцию или отрицание или дизъюнкцию или отрицание. Дальнейшее исключение логических операций, очевидно, невозможно, то есть приведенные пары представляют минимальный базис для построения правильно построенных формул. Однако существует операция, с помощью которой можно представить любую логическую связку. Эта операция получила название «штрих Шеффера» и определяется следующим образом:
На основании этого определения можно ввести следующие законы, выражающие взаимосвязь операции «штрих Шеффера» и других логических связок:
Также следует отметить, что x | y = (x y). К основным законам алгебры логики также относятся следующие:
Еще одним важным законом алгебры логики является закон двойственности. Пусть формула A содержит только операции конъюнкции, дизъюнкции и отрицания. Для операции конъюнкции двойственной считается дизъюнкция, а для дизъюнкции – конъюнкция. Тогда по определению формулы A и A* называются двойственными, если формула A* получается из A путем замены в ней каждой операции на двойственную. Например, для формулы (х y) z двойственной формулой будет (х y) z. Для двойственных формул справедлива следующая теорема: если формулы A и B равносильны, то равносильны и двойственные им формулы, то есть A* = B*. Данную теорему оставим без доказательства. С помощью законов логики можно осуществлять равносильные преобразования. Такие преобразования используются для доказательств, приведения формул к заданному виду, упрощения формул. Под сложностью формул обычно понимается количество символов, используемых для ее записи. То есть формула α проще формулы , если α содержит меньше букв и логических операций. Например, для формулы ( (x y) x y) y можно записать следующую цепочку преобразований, приводящих ее к более простому виду: ( (x y) x y) y = (x y x y) y = (x y) y = y. Функции алгебры логикиЗначение формулы алгебры логики полностью зависит от значений входящих в нее высказываний. Поэтому такая формула может считаться функцией входящих в нее элементарных высказываний. Например, (x y) z является функцией f(x, y, z). Естественно, значения этой функции и входящих в нее элементов могут принимать значения истина или ложь. Тождественно истинные или тождественно ложные функции представляют собой константы. Каждую функцию алгебры логики можно записать в виде формулы или представить таблицей истинности. Как уже было отмечено выше, таблица истинности для n переменных содержит 2n строк. Следовательно, каждая функция алгебры логики принимает 2n значений, состоящих из 0 или 1. Общее же число наборов значений, состоящих из 0 и 1, длины 2n равно 22n. В частности, число различных функций от одной переменной равно четырем.
Из этой таблицы следует, что две функции являются константами f1(x) = 1 и – f2(x) = x, а остальные f3(x) = x и f4(x) = 0. жүктеу/скачать 0.9 Mb. Достарыңызбен бөлісу:
|