I.3. Функции и формулы алгебры логики
Алгебра логики задается двумя множествами: U и Р2, где U – это множество всех высказываний, принимающих значения «истина» или «ложь», или любое другое множество, элементы которого могут принимать одно их двух значений или находиться в одном из двух состояний. Например, множество переключателей, каждый из которых может быть «включен» или «выключен», или множество электрических сигналов, поступающих на вход некоторого устройства, – «сигнал есть» или «сигнала нет» и т.п.. Сопоставим значению «истина» символ «1», а значению «ложь» – символ «0». Таким образом, алгебра логики оперирует на множестве всех высказываний со значениями из двухэлементного множества Е2 ={0, 1}. Множество Р2 – это множество всех таких функций, которые принимают «истинностные» значения 0 или 1, если их аргументы пробегают те же значения. Т.е., если f(x1,x2,…,xn) – истинностная функция от n аргументов или f(x1,x2,…,xn)ÎР2, то она определяет отображение f: ® E2. Алгебра логики занимается изучением свойств этих функций. Истинностные функции называют также функциями алгебры логики, или булевыми функциями, или переключательными функциями. Число всех функций алгебры логики от n переменных равно 22n. Функции алгебры логики могут быть заданы одним из следующих способов: 1) словесное описание; 2) табличное представление; 3) графическое изображение; 4) алгебраическое (в виде формулы). Таблица значений функции алгебры логики называется таблицей истинности или комбинационной таблицей. Ниже приведены таблицы истинности элементарных функций алгебры логики, к которым относятся функции от одной и от двух переменных.
В таблице 1 функция g1(x) – это константа ноль или «противоречие». Функция g2(x) – «тождественная функция x». Функция g3(x) – «отрицание x», обозначается « » или « ». Функция g4(x) – константа единица или «тавтология».
В таблице 2 приведены также обозначения элементарных функций. Эти обозначения (символы) принято называть пропозициональными связками или символами логических операций. Функция f1(x,y) – это так же, как и в таблице 1, константа ноль или «противоречие». Функция f2(x,y)=x&y – «конъюнкция» х и у или «логическое умножение». Читается: «х и у». Значения этой функции можно получить простым умножением значений её аргументов или как наименьшее из значений аргументов, т.е. f2(x,y) = x&y = x×y = min(x, y). Функции f3(x,y)= и f5(x,y)= – это «условное вычитание» у из х, и х из у,соответственно. Их значения можно получить по правилу: и . Функции f4(x,y)=х и f6(x,y)=у – как и в таблице 1, «тождественная функция x» и «тождественная функция у» соответственно. Функция f7(x,y)=хÅу – «сложение по модулю 2» или «исключающее или». Значения этой функции равны остатку от деления на 2 суммы её аргументов. Функция f8(x,y)=хÚу – «дизъюнкция» х и у или «логическое сложение». Читается: «х или у». Значения этой функции можно получить как наибольшее из значений аргументов, т.е. f2(x,y) = xÚy = max(x, y). Функция f9(x,y)=х¯у – «стрелка Пирса» или «отрицание дизъюнкции» или «конъюнкция отрицаний». Последние два названия обусловлены правилом, по которому получаются значения этой функции. Функция f10(x,y)=хºу – «эквиваленция». Читается: «х эквивалентно у». Значения этой функции получаются по правилу: . Функции f11(x,y)= и f13(x,y)= – это так же, как и в таблице 2, «отрицание у» и «отрицание х» соответственно. Функции f12(x,y)= y®x и f14(x,y)= x®y – это так называемая «импликация». Для чтения выражения x®y можно использовать фразу «х влечет у» или «если х, то у». Значения x®y получаются как ответ на вопрос «х меньше, либо равно у?». При этом положительный ответ записывается «1», а отрицательный – «0». Функция f15(x,y)= y | x – «штрих Шеффера» или «отрицание конъюнкции» или «дизъюнкция отрицаний». Последние два названия обусловлены правилом, по которому получаются значения этой функции. Последняя функция в таблице 2 – это так же, как и в таблице 1, константа единица или тавтология. Из пропозициональных переменных, элементарных функций и скобок строятся логические формулы. Вычисление значений формулы выполняется путем подстановки различных наборов значений переменных, входящих в формулу. Результаты вычислений обычно оформляются в виде таблицы истинности формулы. Такие таблицы могут быть полными и сокращенными. Для построения полной таблицы истинности исходную формулу разделяют на подформулы и затем вычисляют значение каждой подформулы. Таким образом, если n – это число переменных в формуле, а s – число выделенных подформул, то число столбцов в полной таблице истинности исходной формулы будет равно n+s, а число строк – 2n. При этом последний столбец этой таблицы будет представлять значения формулы. Для примера рассмотрим построение полной таблицы истинности формулы . Разделим её на подформулы: f1=Øx, f2=f1Úy, f3=f2®z. Тем самым, таблица будет содержать 8 строк и 6 столбцов. См. таблицу 3.
В последнем столбце таблицы 3 находятся значения исходной формулы. Сокращенная таблица истинности строится непосредственно под формулой. Для этого выписывают саму формулу, затем под именами переменных записывают столбцы их значений, а под каждой логической связкой – столбец результатов соответствующей логической операции.
Рассмотрим построение сокращенной таблицы истинности на примере той же формулы: . См. таблицу 4. Внизу таблицы стрелками указаны участвующие в операции столбцы, номером в кружочке отмечен порядок выполняемых действий. Столбец результатов отмечен номером 3. Из рассмотренных примеров видно, что значениями формулы могут быть только 0 или 1. Поэтому столбец результатов можно рассматривать, как некоторую истинностную функцию, принимающую те же значения, что и формула, на соответствующих «энках». Об этой функции говорят, что она реализуется формулой, про формулу, – что она реализует функцию. Две формулы А и В называются эквивалентными, если функции fA и fB, соответствующие им, эквивалентны или равны, т.е. fA=fB. Для обозначения эквивалентных формул традиционно используется запись А=В, которую называют тождеством. Следующие тождества характеризуют важнейшие свойства элементарных функций: {0, 1, Ø, &, Ú}. (Обозначим «∘» любую из функций: {&, Ú, Å}.) 1) ((x∘y)∘z)=(x∘(y∘z)) – свойство ассоциативности; 2) (x∘y)=(y∘х) – коммутативность; 3) конъюнкция и дизъюнкция дистрибутивны друг относительно друга: ((x Ú y) & z) = ((x & z) Ú (y & z)) 4) – закон двойного отрицания; 5) – законы Де Моргана для конъюнкции и дизъюнкции; 6) (х & х) = x; (x Ú x) = x – законы идемпотентности; 7) – закон исключенного третьего; 8) – закон противоречия; 9) (х & 0) = 0, (x Ú 0) = x – умножение на ноль и сложение с нулем; 10) (х & 1) = х, (x Ú 1) = 1 – умножение на единицу и сложение с единицей; 11) ((х & y) Ú x) = x, ((х Ú y) & x) = x – законы поглощения. Все тождества легко проверяются с помощью таблиц истинности. Из свойств элементарных функций следует ряд простых правил преобразования формул: а) если хотя бы один из сомножителей логического произведения равен нулю, то значение произведения также равно нулю; б) если логическое произведение содержит не менее двух сомножителей, один из которых равен единице, то этот сомножитель можно сократить; в) если логическая сумма содержит не менее двух слагаемых, одно из которых принимает значение ноль, то его можно сократить; г) если хотя бы одно из слагаемых логической суммы принимает значение единица, то и вся логическая сумма равна единице; д) пусть U1 – подформула формулы U; если в формуле U заменить любые вхождения подформулы U1 эквивалентной ей формулой В1, то в результате будет получена формула В, эквивалентная исходной формуле U. Для упрощения записи формул вводятся следующие соглашения: 1) В формулах опускают внешнюю пару скобок, т.е. вместо формулы (х®у) пишут выражение х®у. Аналогично в выражениях со знаком отрицания вместо записывают . 2) По закону ассоциативности для операции «∘» вместо формулы ((x ∘ y) ∘ z) или (x∘(y ∘ z)) используется выражение без скобок: x∘ y ∘ z. Для восстановления формулы достаточно расставить скобки, порядок которых не является существенным для вычислений. 3) О старшинстве операций: если в выражении с помощью скобок специально не указан порядок выполнения операций, то одинаковые по старшинству операции выполняются последовательно слева направо. Если в выражении имеются различные операции, то сначала выполняется отрицание, затем конъюнкция, дизъюнкция, импликация и т.д., самой последней выполняется эквиваленция. Скобки восстанавливаются по тому же правилу. Ввиду введенного старшинства операций не всякая формула может быть записана без скобок. Например, в выражениях х®(у®z) или х&(yÚz) дальнейшее исключение скобок невозможно, т.к. это может повлиять на значение, вычисленное по формуле. 4) Для компактности вместо записи х1&x2&…&xs используется запись , а вместо х1Úx2Ú…Úxs – . Перечисленные свойства и правила позволяют преобразовывать формулы, получая новые тождества. Рассмотрим эквивалентные преобразования формулы: 1= 2= 3= 4= 5= Тождество 1 записано по правилу сокращения единичного сомножителя, тождество 2 – по правилу замены подформулы эквивалентной формулой, а именно: здесь для замены использовался закон исключенного третьего. В тождестве 3 применен закон дистрибутивности. Тождество 4 получено по закону коммутативности. И, наконец, тождество 5 записано по закону поглощения, причем для наглядности «поглощающие элементы» подчеркнуты одинарной и двойной чертой.
Популярное: Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (618)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |