Студопедия

КАТЕГОРИИ:



Мы поможем в написании ваших работ!

Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Мы поможем в написании ваших работ!

Решение логических задач методами алгебры логики





Равносильности, выражающие основные законы алгебры логики

хÙу º уÙх — коммутативность конъюнкции.

хÚу º у Úх— коммутативность дизъюнкции.

х Ù (y Ù z) º (х Ú у) Ú z — ассоциативность конъюнкции.

х Ú (у Ú z) º (х Ú у) Ú z — ассоциативность дизъюнкции.

х Ù (у Ú z) º (х Ù у) Ú (х Ù z) — дистрибутивность конъюнкции относительно дизъюнкции.

х Ú (y Ù z) º (х Ú у) Ù (х Ú z) — дистрибутивность дизъюнкции относительно конъюнкции.

Суть применения методов алгебры логики к решению логических задач состоит в том, что конкретные условия логической задачи необходимо представить в виде формул алгебры логики. В дальнейшем путем равносильных преобразований полу­ченную формулу упрощают. Полученная в результате преобразований упрощенная формула, как правило, приводит к ответу на вопрос задачи.

Пример. Пытаясь вспомнить победителей прошлогоднего турнира, пять бывших зрителей турнира заявили:

Антон был вторым, а Борис — пятым.

Виктор был вторым, а Денис — третьим.

Григорий был первым, а Борис — третьим.

Антон был третьим, а Евгений — шестым.

Виктор был третьим, а Евгений — четвертым.

Впоследствии выяснилось, что каждый зритель ошибся в одном из двух своих высказываний. Каково было истинное распределение мест в турнире?

Обозначим участника первой буквой его имени, нижний индекс около буквы (цифра) будет обозначать номер места, которое он занял в турнире, то есть в вы­ражении Ху имеем, что X — это участник турнира, а у — номер места, которое он занял в турнире. Обозначим буквой L истинное распределение мест в турнире (1 = 1).

Так как в паре высказываний каждого зрителя одно истинно, а второе ложно, то дизъюнкции этих высказываний будут истинными:

Л2у Б5= 1.

В-2 v Дз = 1.

Г{ vft-l.

А3 v Е6= 1.

B3vEAml.

Тогда будет истинной формула

L ■ (Л2 v Б5) а (В2 v Дз) д (Г, v Б3) л (Л3 v Е6) л (В3 v ЕА).



Исходя из данных условия, можно начать преобразования. Поскольку одно из входящих в дизъюнкции высказываний обязательно истинно, а второе обязатель­но ложно, то за отправную точку в преобразованиях можно принять пару ^ v б5 = 1. В этой паре высказывание Гх является истинным, а Б3 — ложным, поскольку на первое место нет других претендентов. Тогда, используя равносильность х v О ■ ху получаем Гх v 0 = Ги и формула приводится к виду

1з(А, vБ5)л(В2 v Д5)лГ! л(А, v£6)л(В3 vE4).

Поскольку вариант Б3 оказался ложным, а других претендентов на пятое место нет, то истинным будет вариант Б5. Тогда в первой по счету паре, применив ту же равносильность, что и на предыдущем шаге, мы также оставляем одно высказы­вание, и основная формула принимает вид

L = Б5 а (В2 v Д3) л Г{ л (А3 v Е^) л (2?3 v ЕА).

Продолжая эти равносильные преобразования, приводим формулу к виду

L = Б5 а В2 а Г х л А3 а Е4.

Отсюда следует, что Б5 = 1, В2 * 1, ^ = 1, А3 = 1, ЕА = 1, то есть первым был Григо­рий, вторым — Виктор и т. д. Это и является ответом на вопрос, поставленный в задаче.


Булева алгебра

Без булевой алгебры было бы невозможно создание таких устройств, как со­временные компьютеры, в состав центральных процессоров которых входят мил­лиарды электронных переключателей.

Рассмотрим непустое множество М элементов любой природы (г, г/, 2,...}, в ко­тором определены отношение равенства (=) и три операции: сложение (+), умно­жение (•) и отрицание О, подчиняющиеся следующим законам:

 

 

Такое множество М называют булевой алгеброй.

Если под основными элементами х, г/, 2,... подразумевать высказывания, под операциями сложения, умножения и отрицания булевой алгебры — соответственно, дизъюнкцию, конъюнкцию и отрицание алгебры высказываний, а знак равенства рассматривать как знак равносильности, то, как следует из равносильностей алге­бры высказываний, все аксиомы булевой алгебры выполняются.

В тех случаях, когда для некоторой системы аксиом удается подобрать конкрет­ные объекты и конкретные соотношения между ними так, что все аксиомы выпол­няются, говорят, что найдена интерпретация, или модель, данной системы аксиом.

Значит, алгебра логики является интерпретацией булевой алгебры. Булева алгебра имеет и другие интерпретации. Например, если под основными элемен­тами х, г/, 2,... множества М подразумевать множества, под операциями булевой

алгебры — соответственно, объединение, пересечение и дополнение множеств, а под знаком равенства — знак равенства множеств, то мы приходим к алгебре множеств. Нетрудно убедиться, что и в алгебре множеств все аксиомы булевой алгебры выполняются.

 

 

Ясно, что тождественно истинные и тождественно ложные формулы алгебры логики представляют собой постоянные функции, а две равносильные формулы выражают одну и ту же функцию.

Каково количество функций п переменных? Очевидно, каждую функцию ал­гебры логики (как и формулу алгебры логики) можно задать с помощью таблицы истинности, которая будет содержать 2п строк. Следовательно, каждая функция п переменных принимает 2п значений, состоящих из нулей и единиц. Таким обра­зом, функция п переменных полностью определяется набором значений из нулей и единиц длины 2п. Общее же количество наборов, состоящих из нулей и единиц длины 2п равно 22”. Значит, количество различных функций алгебры логики п переменных равно 22”.

В частности, различных функций одной переменной четыре, а различных функ­ций двух переменных — шестнадцать. Выпишем все функции алгебры логики одной и двух переменных.

Рассмотрим таблицу истинности для различных функций одной переменной. Она, очевидно, имеет вид

X fix) /г(*) /з(*) Мх)

 

Из этой таблицы следует, что две функции одной переменной будут постоян­ными: f\(x) = 1 и f4(x) = 0, a f2(x) я х и/3(г) = х.

Таблица истинности для всевозможных функций двух переменных имеет вид



X У / Л л fj л /9   /12 /13 и /l5 /16

 

Ясно, что аналитические выражения этих функций могут быть записаны сле­дующим образом:

 

 

Построение коммутационных схем на основе





Дата добавления: 2014-01-03; Просмотров: 1029; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.004 сек.