Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Применение основных равносильностей алгебры высказываний для решения содержательных задач, требующих приведения формул алгебры логики к минимальной кнф и сднф виду.Содержание книги
Поиск на нашем сайте
Приведение формул к виду СДНФ бывает необходимо при решении конкретных, содержательных задач. Если, например, в условиях задачи речь идет об элементарных высказываниях А, В, С и если условия задачи записаны в виде формулы, то, приведя эту формулу к виду СДНФ, мы тем самым получим полный перечень всех тех случаев, при которых условия задачи будут выполнены. Рассмотрим конкретный пример. Задача. Известно, что если Андрей и Володя пойдут в кино, то Сережа в кино не пойдет. Известно также, что если Володя не пойдет в кино, то в кино пойдут Андрей и Сережа. Надо узнать, кто при этих условиях может пойти в кино. Решение. Введем обозначения. Пусть А означает: «Андрей пойдет в кино», В означает: «Володя пойдет в кино», С означает: «Сережа пойдет в кино». Условия задачи запишутся следующим образом: Воспользуемся теперь равносильностью . (Эта равносильность легко устанавливается с помощью таблиц истинности.) На основании этой равносильности условия задачи примут вид: . Так как оба условия задачи должны быть выполнены, то должна быть истинной их конъюнкция. Составим эту конъюнкцию и приведем ее к виду ДНФ: Условия задачи свелись к формуле , которая должна быть истинной. Но дизъюнкция истинна, если истинным будет хотя бы один из ее членов. Значит, для того, чтобы условия задачи были выполнены, достаточно, чтобы имел место один из трех случаев: 1. , т. е. в кино может пойти Володя без Андрея. 2. , т. е. в кино могут пойти Андрей с Сережей, но без Володи. 3. , т. е. в кино может пойти Володя без Сережи. Задача как будто бы решена. Но на самом деле это решение нельзя признать окончательным, так как в первом и третьем случае ответ будет неполным. Чтобы получить полный ответ, нужно ранее полученную ДНФ преобразовать к СДНФ. Теперь мы действительно получили полный перечень всех случаев, при которых выполняются условия задачи, к тому же выяснилось, что таких случев не три, а четыре. Возникает вопрос: зачем нужны преобразования, приводящие исходные формулы к минимальной форме? Зачем нужна минимальная КНФ? Ответ заключается в том, что все это совершенно необходимо при решении задач. Рассмотрим конкретный пример. Задача. В школе решили организовать секцию атлетической гимнастики. Надо было разработать правила приема в эту секцию. Ребята внесли ряд предложений: 1. Если ученик не отличник и не здоров, то он не может быть принят. 2. Если ученик является отличником, то не может быть, чтобы он был здоров и его не приняли. 3. Если ученик не принят, то он не отличник. 4. Если ученик не здоров, то он не отличник и не будет принят. Учитель физкультуры сказал, что четыре правила — это слишком много. К тому же формулировки правил должны быть более простыми, более лаконичными. Поэтому, сказал учитель, возникает следующая задача: надо совокупность всех четырех правил заменить новыми правилами — и надо это сделать так, чтобы число новых правил было минимальным, чтобы каждое новое правило было сформулировано кратчайшим образом и чтобы совокупность новых правил была равносильна совокупности четырех исходных правил. Через некоторое время эту задачу действительно удалось решить. Какие правила получились? Решение. Обозначим элементарные высказывания: ученик является отличником — О, ученик здоров — 3, ученик принят — П. Теперь мы можем записать исходные правила в символической форме. Полученные формулы мы сразу же упростим, воспользовавшись равносильностью , законом де Моргана и законом снятия двойного отрицания . Мы получим следующие цепочки равносильностей: 1. ; 2. ; 3. ; 4. . Так как все четыре условия должны выполняться, то должна быть истинной их конъюнкция. Составим эту конъюнкцию и приведем ее к минимальной дизъюнктивной форме. Мы получим следующий результат: . Некоторые учащиеся, которые впервые решают задачу подобного рода, считают, что решение уже найдено. По их мнению, получилось два новых правила: и . На самом же деле ответ будет совсем другим. Чтобы понять, в чем тут дело, рассмотрим внимательно полученный результат. Формула представляет собой дизъюнкцию, а дизъюнкция истинна тогда и только тогда, когда истинным является хотя бы один из ее компонентов. Может, например, оказаться, что истинно только или только . Когда же учащиеся, получив формулу , считают, что они тем самым получили два правила, т. е. два истинных утверждения, то они совершают грубую ошибку. Ведь из истинности дизъюнкции вовсе не следует, что истинны оба ее компонента. Чтобы найти новые правила приема в спортивную секцию, надо рассуждать совсем по-другому. Начнем с того, что искомые правила должны представлять собой истинные высказывания. Но если высказывания истинны, то истинна и их конъюнкция, а если истинна конъюнкция, то истинно и каждое из высказываний в отдельности. Значит, чтобы найти новые правила, достаточно найти конъюнкцию этих правил. Следовательно, мы должны полученную ранее формулу преобразовать в конъюнкцию. А так как число новых правил должно быть минимальным и так как каждое правило должно быть сформулировано кратчайшим образом, то искомая конъюнкция должна иметь вид минимальной КНФ. Чтобы выполнить это преобразование, воспользуемся законом исключенного третьего и законом поглощения. Мы получим следующую цепочку равносильностей:
= Таким образом, задача решена. Получилось два правила приема в секцию: 1. Если ученик является отличником, то он будет приняв ; 2. Если ученик принят, то необходимо, чтобы он был| здоров . Аудиторная самостоятельная работа №11 «Приведение формул алгебры высказываний к КНФ, ДНФ, СКНФ и СДНФ виду» Задание №1. В коробке лежат шары – деревянные и пластмассовые, большие и маленькие, зеленые и красные. Из коробки надо достать шар, соблюдая следующие правила: 1. Шар может быть деревянным только тогда, когда он маленький и зеленый; 2. Если шар маленький, то для того, чтобы он был пластмассовым, достаточно, чтобы он не был зеленым. 3. Если шар маленький и красный, то он деревянный. Известно, что эти правила сводятся к двум простейшим условиям. Когда же вынули шар, оказалось, что из двух простейших условий выполнено только одно. Кроме того, о вынутом шаре известно, что он либо зеленый, либо большой и деревянный. Какой шар вынули из коробки? (20 баллов)
Задание №2. Приведите формулу к минимальной КНФ: (10 баллов) Задание №3. Приведите формулу к минимальной ДНФ:
(10 баллов) Задание №4. Приведите формулу к минимальной СКНФ:
(10 баллов)
|
||||
Последнее изменение этой страницы: 2016-12-26; просмотров: 391; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.191.223.30 (0.008 с.) |