Понятие формулы исчисления высказываний
Глава 20. Формулы исчисления высказываний.
Исчисление высказываний
Глава 20. Формулы исчисления высказываний.
Логика высказываний
Понятие формулы исчисления высказываний
Глава 20 Формулы исчисления высказываний Общие сведения Упражнения Вычисление значения постоянной логической формулы Вычисление значения формулы в заданной интерпретации Соотношение формул Построение таблицы истинности Упражнение Определение выполнимой, общезначимой и противоречивой формулы Логическое следствие Представление утверждений формулами Задача о хищении Упражнение Теоремы о логическом следствии Пример использования теоремы 1 о логическом следствии Упражнение Задание по программированию Пример использования теоремы 2 о логическом следствии Задача о рыцарях и лжеца Упражнения Конъюнктивная нормальная форма и ее построение Теорема Упражнение Построение формулы в конъюнктивной нормальной форме Алгоритм построения КНФ Упражнения Автоматизация ввода логических формул Метод резолюций Теорема о резольвенте Пример использования теоремы о резольвенте Упражнения Задание по программированию Теорема о полноте метода резолюций Задача о поиске виновного Задача о влюбленном логике Упражнения Задание по программированию Методы сокращения множества дизъюнктов Правило тавтологии Правило однолитерных дизъюнктов Задача о влюбленном логике с применением правила однолитерного дизъюнкта Правило чистых литералов Правило расщепления Пример использования правила чистого литерала Пример использования правила расщепления Задача об искателе приключений Упражнения Задания по программированию Занимательные задачи Прекраснейшая богиня Игроки на скачках Поиск пути выхода из лабиринта Расследование преступления Обвинитель на острове рыцарей и лжецов Суд на острове рыцарей и лжецов Любовь рыцаря или лжеца Интервью на острове рыцарей и лжецов Путешественник на островах Исследование шестого острова Поиск виновных Искатель приключений. В предыдущих главах для самострятельной работы предлагались упражнения, которые располагались в конце каждой главы. При выполнении упражнения следовало написать сценарий решения некоторой задачи. В настоящей главе изложение материала будет изменено. Упражнение может быть предложено сразу после рассмотрения теоретического материала или примера, иллюстрирующего теорию. Кроме того, упражнения не обязательно предполагают создание сценария. Отдельно формулируется задание на создание сценария. Материал этой главы посвящен введению в один из разделов искусственного интеллекта — автоматическое доказательство теорем. В обычной жизни человек принимает решения в зависимости от конкретной ситуации. Предположим, что нам известны некоторые факты или ранее уже доказанные утверждения F1, F 2, Утверждение, что G логически следует из утверждений F1, F 2, Доказательство теоремы — рассуждения, позволяющие установить, что теорема верна. Математическая логика — наука о правильных математических рассуждениях, о математическом мышлении. Впервые правила рассуждений систематизировал Аристотель. Однако как наука математическая логика сложилась лишь в середине XIX века, когда Джордж Буль ввел логические связки и исчисление высказываний. Одной из задач математической логики является формализация понятия доказательства. Для описания утверждений можно использовать формулы исчисления высказываний. Каждое высказывание либо истинно, либо ложно. Логические константы "истина" и "ложь" будем обозначать буквами И и Л соответственно. Логические переменные в математической логике их называют пропозициональные переменные будем обозначать большими буквами латинского алфавита. В исчислении высказываний логические константы и логические переменные называются атомами и считаются простейшими логическими формулами. Других формул в исчислении высказываний нет. Мы видим, что при построении сложных логических формул появляется большое количество круглых скобок. Для сокращения их числа можно использовать старшинство логических связок. Самой старшей является унарная связка "отрицание", которая выполняется в первую очередь и применяется к непосредственно следующей за ней формуле.. Бинарные логические связки, приведенные выше в таблице истинности, перечислены по убыванию их старшинства. Связки одного старшинства применяются в порядке их следования слева направо. Если учитывать старшинство операций, то часть скобок можно опустить. Формулу исчисления высказываний будем называть постоянной, если она не содержит переменных. Далее, вычисляя сначала выражения в скобках по таблице истинности, получаем значение всей формулы — истина. Предположим, что мы разговорились с тремя жителями А, В и С, о каждом из которых известно, что он либо рыцарь, либо лжец. Рыцари всегда говорят правду, лжецы всегда лгут. Двое из них А и В высказали следующие утверждения. Вычисление значения постоянной логической формулы. Создадим сценарий, который облегчает ввод постоянных пропозициональных формул. При нажатии кнопки, соответствующей логическим константам или логическим операциям, определенная операция появляется в поле ввода так, как показано на рис. После построения формулы и нажатия кнопки Вычислить определяется значение формулы. Напомним, что при построении логических формул в языке JavaScript разрешено использовать три логические операции: При нажатии кнопки соответствующая операция появляется в текстовом поле, причем знак операции должен быть тем, который принят в языке JavaScript. Подобная формула может быть вычислена, если подать ее в качестве параметра методу eval. HTML-код документа, содержащего сценарий решения задачи, представлен в листинге Если задать значения всем входящим в формулу переменным, то можно вычислить результат всей формулы. В этом случае говорят, что задана интерпретация. В исчислении высказываний каждой формуле соответствует конечное число интерпретаций. Вычисление значения формулы в заданной интерпретации. Необходимо написать сценарий вычисления значения логической формулы в заданной интерпретации. Пусть при построении формулы используются только три переменные а, b, с, значения которых указывает пользователь. Для ввода логической формулы применяется построитель формул так, как показано на рис. В общем случае при анализе формулы следует учесть количество различных переменных, входящих в формулу. Так как каждая переменная может принимать только два значения, то число различных интерпретаций конечно. Формулы бывают тождественно истинными или общезначимыми — это формулы истинные в любой интерпретации. Тождественно ложными или противоречивыми называются формулы, ложные в любой интерпретации. Наконец, выполнимыми называются формулы, допускающие указание интерпретации, в которой эта формула истинна. Если две формулы имеют одинаковые значения при любых возможных интерпретациях, то говорят, что они равнозначны или эквивалентны. Равнозначность формул обозначают знаком о. Наиболее распространенные равнозначные формулы приведены в табл. Нетрудно доказать, что любую формулу исчисления высказываний можно преобразовать к равнозначной формуле, которая содержит только три логические связки: Некоторые часто используемые правила получили специальные названия, например:. Требуется определить, эквивалентны ли они. Для того чтобы решить задачу, мы переберем все интерпретации и в каждой из интерпретаций вычислим значение формулы. Результаты приведены в табл. После вычислений видно, что значения формул не совпадают в некоторых интерпретациях, поэтому заданные формулы неравнозначны. Напишем сценарий, который для логической формулы строит таблицу истинности. В формуле разрешено использовать операции отрицания, дизъюнкции и конъюнкции; переменные представляются буквами латинского алфавита. Вид документа представлен на рис. Если после ввода формулы нажать кнопку Таблица истинности, то будет выведена таблица, в которой указаны все возможные интерпретации и значение формулы в каждой интерпретации. Для формулы, введенной в строку на рис. HTML-код документа, который по заданной формуле строит таблицу истинности, приведен в листинге Функция, осуществляющая построение таблицы, хранится во внешнем файле. Содержимое файла приведем позже, а пока рекомендуется написать сценарий в качестве упражнения. Для каждой из следующих формул определите, является ли она общезначимой, противоречивой или выполнимой:. Определение выполнимой, общезначимой и противоречивой формулы. Напишем сценарий, который определяет, является ли заданная формула выполнимой, общезначимой или противоречивой. Для простоты будем считать, что в формуле используются операции отрицания, конъюнкции и дизъюнкции. При анализе формулы перебираются интерпретации. Вычисляется значение формулы в начальной интерпретации, а затем, если при переходе к следующей интерпретации значение формулы изменилось на противоположное, то она выполнима. Если же при всех интерпретациях значение формулы не изменилось, то она либо общезначима, либо противоречива. Результат выполнения сценария представлен на рис. Если формула выполнима, то кроме определения типа формулы требуется построить таблицу истинности. Как и в предыдущем случае, функция, осуществляющая анализ формулы, хранится во внешнем файле. При решении многих задач нас интересует, следует ли некоторое утверждение из ранее доказанных или уже известных. Мы введем понятие логического следствия и с его помощью решим некоторые задачи. Пусть даны формулы F1, F2, Говорят, что G логическое следствие формул F1, F2, Предположим, что некоторый человек вас спрашивает: Запишем утверждения формулами исчисления высказываний, обозначив через В утверждение "Я люблю Бетти", через D — "Я люблю Джейн". Тогда посылка утверждение "Если это верно, то я люблю Бетти" запишется формулой:. Предполагаемый ответ следствие — формулой В. Переберем возможные значения переменных В и D, вычислим значения формул F и G. Полученные данные оформим в виде табл. Нас интересуют только те интерпретации, в которых формула F истинна. В этих интерпретациях истинна и формула G. Согласно определению формула G — логическое следствие формулы F. Таким образом, мы выяснили, что ответ на вопрос "Люблю ли я Бетти? На складе совершено хищение. Подозрение пало на трех человек: Они были доставлены для допроса. Запишем приведенные утверждения с помощью формул исчисления высказываний. На основании определения логического следствия выясним, является ли ответ на вопрос логическим следствием этих трех утверждений. Обозначим через А утверждение "А виновен", через В — "В виновен", через С — "С виновен". Запишем утверждения 1—3 с помощью формул F1 - F3 исчисления высказываний:. Предполагаемый ответ — "В виновен" — обозначим через G. Проверим, является ли формула 7 логическим следствием формул F1, F2, F3. Таких интерпретаций только две — вторая и шестая. В этих интерпретациях и значение формулы G истинно. Следовательно, формула G— логическое следствие, т. На этот раз на допрос были вызваны четыре подозреваемых: А, В, С, D. Было доказано, что, по крайней мере, один из них виновен и никто кроме А, В, С, D в ограблении не участвовал. Кроме того, удалось установить следующее. Кто же из подозреваемых граждан виновен? Докажите это, воспользовавшись понятием логического следствия. Теоремы о логическом следствии позволяют решение вопроса о том, является одно утверждение следствием других, свести к анализу общезначимости или противоречивости некоторой формулы. Тогда формула G является логическим следствием формул F1, F2, Предположим, что G— логическое следствие. Возьмем произвольную интерпретацию I. Рассмотрим сначала случай, когда эта формула истинна. Тогда истинны и все формулы Fi. Так как формула G— логическое следствие, то она истинна, если истинны посылки. Таким образом, и вся импликация. Мы выбрали произвольную интерпретацию и доказали, что исследуемая формула в ней истинна. Таким образом, если G — логическое следствие, то формула. Докажем, что формула Алогическое следствие формул F1, F2, Нас интересуют интерпретации, в которых истинны посылки. Выберем одну из них. Тогда формула G также должна быть истинной. Согласно теореме 1 формула G является логическим следствием тогда и только тогда, когда формула. В результате преобразований получили требуемую формулу, и она противоречива. Пример использования теоремы 1 о логическом следствии. Предположим, что вас спрашивают: Любите ли вы Маргарет? Пусть через Е обозначено утверждение "Я люблю Еву", через М — "Я люблю Маргарет". Утверждение "Если вы любите Еву, то вы любите Маргарет" запишется формулой: Расследуется простое дело о хищении со склада. Преступник или преступники вывезли награбленное имущество на машине. Подозрение пало на трех человек А, В, С, которые были доставлены в Скотланд-Ярд для допроса. Напишите сценарий, который определяет, является ли некоторая формула следствием заданных пользователем формул, опираясь на теорему 1 о логическом следствии. Пример использования теоремы 2 о логическом следствии. Рассмотрим предыдущий пример и ответим на вопрос: На некотором острове, населенном рыцарями и лжецами напомним, что рыцари говорят только правду, лжецы — ложь , разнесся слух о том, что на нем зарыты сокровища. Вы прибываете на остров и спрашиваете одного из местных жителей назовем его А , есть ли на острове золото. В ответ на ваш вопрос А заявляет: Ответим на второй вопрос. Обозначим через А утверждение "А — рыцарь", через L — "Сокровища на острове есть". Тогда высказывание жителя А "Сокровища на острове есть в том и только том случае, если я рыцарь" запишется формулой:. Если А — рыцарь, то его высказывание истинно; если лжец, то ложно, таким образом, наша посылка — формула вида. Для того чтобы доказать, что утверждение L — следствие нашей посылки, т. Проверим это, перебрав все интерпретации и вычислив значение формул в каждой из них. Этих данных недостаточно, чтобы доказать виновность каждого из трех подсудимых в отдельности, но эти данные позволяют отобрать двух подсудимых, о которых известно, что один из них заведомо виновен. Определите и докажите, о каких подсудимых идет речь. Мы видим, что если задача такова, что ее посылки постулаты и следствие записываются формулами исчисления высказываний, то решить задачу можно одним из следующих способов:. Конъюнктивная нормальная форма и ее построение. Во многих случаях удобно рассматривать формулы специального вида или, как говорят, формулы в канонической форме. В математической логике и в теории автоматического доказательства теорем рассматриваются формулы в конъюнктивной нормальной форме. Литералом называется атом или отрицание атома. Дизъюнктом называется литерал или дизъюнкция литералов. Формула находится в конъюнктивной нормальной форме КНФ , если она представляет собой либо дизъюнкт, либо является конъюнкцией дизъюнктов. По любой формуле F может быть построена эквивалентная ей формула G, находящаяся в КНФ. Идею доказательства теоремы и построения КНФ поясним на примере формулы Fот трех переменных. Возьмем следующую формулу F:. Правый столбец таблицы будем использовать для построения дизъюнктов конъюнктивной нормальной формы, соответствующей формуле. Выделим те интерпретации, в которых формула принимает значение "ложь", и для этих интерпретаций построим дизъюнкт по правилу: В нашем случае формула G является конъюнкцией построенных формул:. Формулы F и G эквивалентны и G имеет КНФ. Эквивалентность формул можно доказать в качестве упражнения. Построение формулы в конъюнктивной нормальной форме. Напишем сценарий, который на основании рассмотренной теоремы по произвольной формуле строит эквивалентную формулу, находящуюся в КНФ. В текстовое поле вводится формула, после щелчка по кнопке, формируется эквивалентная формула, находящаяся в КНФ. Один из тестов продемонстрирован на рис При построении КНФ перебираются все интерпретации, исследуется значение формулы в текущей интерпретации, и, если значение ложно, то соответствующая формула добавляется в строку результата. Вместе с формулой в конъюнктивной нормальной форме выдается таблица истинности так, как показано на рис. Три функции построение таблицы истинности, анализ типа формулы и построение КНФ хранятся во внешнем файле. Приведем содержимое HTML-документа, содержащего требуемые функции листинг Один из способов построения формулы в КНФ мы уже продемонстрировали. Заметим, что КНФ G формулы F можно получить, выполняя последовательно эквивалентные преобразования формулы F. Алгоритм преобразования может быть таким:. Сначала следует исключить из формулы знаки логической эквивалентности и импликации, применяя последовательно правила эквивалентности:. Нетрудно доказать, что произвольная пропозициональная формула эквивалентна дизъюнкции элементарных конъюнкций, соответствующих тем интерпретациям, при которых данная формула истинна. Автоматизация ввода логических формул. Необходимо создать сценарий, который облегчает ввод логических формул. При нажатии кнопок, сопоставленных переменным, скобкам или логическим операциям, соответствующая операция появляется в поле ввода. После формирования формулы в текстовом поле при щелчке по кнопке вычисляется таблица истинности, определяется тип формулы, строится соответствующая формуле конъюнктивная или дизъюнктивная нормальные формы так, как показано на рис. В последних рассмотренных примерах использовались три логические операции. Это облегчало написание алгоритмов анализа формулы, т. Рассмотреть варианты решения предложенных задач в случае, когда в формуле используются импликация и эквивалентность, читателю предлагается самостоятельно. Теперь нам надо показать, как из уже имеющихся знаний можно извлекать новые утверждения. Введем правило резолюции, согласно которому из двух рассуждений можно вывести третье. Пусть С1 и C2 — два дизъюнкта. Литерал L1 из дизъюнкта C1 , литерал L2 из дизъюнкта C2. Причем литералы L1 и L2 образуют контрарную пару. Резольвентой дизъюнкто в C1 и С2 называется дизъюнкт С , составленный из С1 вычеркиванием L1 и из C2 вычеркиванием L2. Такой дизъюнкт называется резольвентой первых двух. Выводом в методе резолюций дизъюнкта С из множества S называется последовательность дизъюнктов С1, C2 , Вывод можно рассматривать как формализованный аналог понятия доказательства. Вывод тождественно ложного дизъюнкта называется опровержением. Пусть даны два дизъюнкта С1 и C2- Резольвента С дизъюнктов С1 и C2 является их логическим следствием. Резольвента позволяет переходить от двух рассуждений к третьему, а теорема о резольвенте гарантирует, что если исходные утверждения были истинными, то истинным будет и построенное утверждение, т. Предположим, что дизъюнкты С1 и С2 истинны в произвольно взятой интерпретации I. Нам требуется доказать, что резольвента С также истинна в этой интерпретации. А поскольку значение дизъюнкта Q истинно, то и резольвента истинна. Если же значение литерала L в выбранной интерпретации ложно, то истинным должно быть значение дизъюнкта Р, т. Как и в предыдущем случае, резольвента будет иметь значение "истина". Таким образом, резольвента является логическим следствием дизъюнктов, по которым она построена. Пример использования теоремы о резольвенте. Тогда приведенные рассуждения записываются формулами:. Последняя формула, очевидно, соответствует рассуждению: Напишите сценарий, который по двум заданным дизъюнктам строит резольвенту, если это возможно. Теорема о полноте метода резолюций. Множество дизъюнктов S противоречиво тогда и только тогда, когда существует опровержение в S или из S. Предположим, что мы построили опровержение во множестве дизъюнктов S, вывод имеет вид: Докажем, что множество дизъюнктов S противоречиво. Предположим, что это не так, множество S выполнимо и, следовательно, существует интерпретация S, в которой все дизъюнкты из S истинны. Каждое D, в опровержении либо из множества S и является истинным, либо представляет из себя логическое следствие предыдущих дизъюнктов и также истинно по теореме о резольвенте. Но тогда и последний дизъюнкт истинен, чего не может быть, потому что последний дизъюнкт в опровержении тождественно ложная формула. Вернемся к сформулированной ранее задаче. Пусть у нас есть аксиомы или уже доказанные факты F1, F2, Нам требуется определить, следует ли утверждение G из фактов F1, F2, По теореме 2 о логическом следствии для решения этого вопроса нам достаточно определить, является ли формула. Эту формулу можно преобразовать к КНФ и рассматривать в дальнейшем множество дизъюнктов S: По теореме о полноте метода резолюций, для того чтобы определить противоречивость невыполнимость множества S, достаточно найти опровержение в S. В совершении преступления подозреваются четверо человек: Будем считать, как и раньше, что через А обозначено утверждение "А виновен", через В— "В виновен", через С—"С виновен" и, наконец, через D — "D виновен". Запишем четыре известных факта и ответ на вопрос формулами исчисления высказываний:. Построив опровержение в методе резолюций, мы по теореме о полноте метода резолюций доказали, что множество дизъюнктов противоречиво, следовательно, рассматриваемая формула противоречива. По теореме 2 утверждение G — логическое следствие, т. Перед нами три девушки: Сью, Марция и Диана. Предположим, что юноша, занимающийся математической логикой, высказывает следующее. На основании теоремы о полноте метода резолюций делаем вывод о том, что автор высказываний любит Диану. Постройте опровержение для решения следующей задачи. На острове рыцарей и лжецов за преступление судили двух жителей. Обвинитель, однако, оказался также жителем острова. Три человека, А, В и С, проживают на острове рыцарей и лжецов. Условимся называть двух людей однотипными, если они оба рыцаря или оба лжеца. Пусть А и В высказывают следующие утверждения:. Напишите сценарий, который по заданной последовательности дизъюнктов определяет, может ли она быть выводом в данном множестве дизъюнктов. Методы сокращения множества дизъюнктов. Мы исследуем вопрос, является ли противоречивым множество дизъюнктов S. Однако это множество может быть достаточно велико, поэтому искать вывод из большого множества дизъюнктов иногда затруднительно. Возникает вопрос, можно ли как-нибудь это множество сократить? Математики Девис и Патнем предложили несколько правил, которые позволяют сократить исходное множество дизъюнктов. Из множества дизъюнктов S можно вычеркнуть все дизъюнкты, которые являются тавтологиями. Оставшееся множество дизъюнктов противоречиво тогда и только тогда, когда противоречиво множество S. Если во множестве S существует однолитерный дизъюнкт L, то множество Si получается из S вычеркиванием всех дизъюнктов, содержащих L. Если построенное Si пусто, то исходное S выполнимо. Для доказательства выполнимости S достаточно рассмотреть интерпретацию, в которой значение L истинно. Множество дизъюнктов 52 противоречиво тогда и только тогда, когда противоречиво множество S. Задача о влюбленном логике с применением правила однолитерного дизъюнкта. Мы рассмотрели ранее задачу о влюбленном логике и трех девушках: Сью, Марции и Диане. Для решения вопроса о том, любит ли человек, высказывающий четыре утверждения, Диану, мы строили опровержение в методе резолюций. Однако решить эту задачу можно, применяя к построенному множеству дизъюнктов правило однолитерного дизъюнкта. Рассмотрим множество дизъюнктов S: В последнем множестве опять есть единичный дизъюнкт, после применения правила получаем противоречивое множество, следовательно, и исходное множество S противоречиво, т. D — логическое следствие. Если L — чистый литерал, то вычеркиваем из S все дизъюнкты, содержащие L. Оставшееся множество дизъюнктов обозначим через Si. Множество дизъюнктов Si противоречиво тогда и только тогда, когда противоречиво множество S. Множество S противоречиво тогда и только тогда, когда оба множества S1 и S2 противоречивы. Пример использования правила чистого литерала. В этом множестве есть чистый литерал А. Применим к множеству дизъюнктов правило чистого литерала. Множество после применения правила чистого литерала будет следующим:. Пример использования правила расщепления. В некоторых случаях удается решить задачу, используя лишь правила сокращения дизъюнктов. Продемонстрируем такую возможность при решении следующей задачи. Предположим, что некоторый искатель приключений хочет добраться до острова сокровищ. Путешественнику предложили три карты: Только одна из карт правильная и указывает путь к острову сокровищ. В комнате, где лежали карты, находились пятеро колдунов: Каждый колдун был либо рыцарем, либо лжецом и каждый дал путешественнику совет:. Докажем, что Y — правильная карта. Будем, как ранее, обозначать через А утверждение "А — рыцарь" аналогично для В, С, D и Е. Обозначим через X утверждение "X— правильная карта" аналогично для Y и Z. Запишем сначала советы колдунов и предполагаемое следствие формулами исчисления высказываний:. Применим к множеству S правило единичного дизъюнкта дизъюнкт Е , получим множество S1: К построенному множеству S2 применим правило расщепления по дизъюнкту А, получим два множества S4 и S5: Во множестве S4 есть чистый литерал X. По правилу чистого литерала все дизъюнкты, содержащие этот литерал, можно исключить из рассматриваемого множества. Применяя к S5 правило чистого литерала, а затем правило единичного дизъюнкта, получаем противоречивое множество. Следовательно, утверждение Y— логическое следствие утверждений FI—FS, таким образом, карта Y — правильная карта и поиск сокровищ можно продолжать. Перед нами три островитянина, А, В, С, каждый из которых либо рыцарь, либо лжец. Двое из них высказывают утверждения. Путешественник проснулся на острове рыцарей и лжецов, название которого он не помнит. Он разговорился с двумя местными жителями А и В, которые сообщили ему следующее. Оказалось, что каждая из трех девушек права только в одном из своих высказываний. Какой марки автомобиль, и в какой стране изготовлен? Постройте множество дизъюнктов и примените для сокращения к нему правила Девиса и Патнема. Напишите сценарий, который сокращает заданное множество дизъюнктов по правилам Девиса и Патнема. Напишите сценарий, который проверяет правильность построения формулы исчисления высказываний методом рекурсивного спуска. Напишите сценарий, который для заданной пропозициональной формулы находит все подформулы, значения которых совпадают с заданным. Напишите сценарий, который по формуле исчисления высказываний, представленной в инфиксной нотации, строит формулу в префиксной нотации. Напишите сценарий, который вычисляет значение пропозициональной формулы, находящейся в постфиксной нотаций. Напишите сценарий, при выполнении которого пропозициональная формула преобразуется таким образом, что знак отрицания встречается лишь перед переменной. Заданы две пропозициональные формулы. Напишите сценарий, который проверяет, являются ли формулы эквивалентными. Переменная х в формуле А называется фиктивной, если существует формула В, эквивалентная формуле А, и не содержащая вхождений переменной х. Напишите сценарий, который находит в заданной формуле все фиктивные переменные. Напишите сценарий, который по заданной пропозициональной формуле определяет, верно ли, что на наборах противоположных значений переменных формула принимает противоположное значение. Пара скобок в пропозициональной формуле называется избыточной, если после ее удаления формула остается эквивалентной исходной формуле. Напишите сценарий, который удаляет все избыточные пары скобок. Если задача описывается с помощью формул исчисления высказываний, то многие этапы решения задачи определение общезначимости, противоречивости или выполнимости формул, приведение к КНФ, сокращение множества дизъюнктов и др. Полученные знания рекомендуется применить при создании сайта, позволяющего пользователю решать логические задачи и проверять правильность решения. Для выбранной из предложенного списка задачи пользователю требуется ввести формулы, соответствующие условию задачи, и указать предполагаемое следствие. Созданный сценарий должен проверять правильность решения задачи любым из описанных способов. Предлагается следующий список задач, который может быть дополнен или изменен разработчиком. В одном старинном задачнике описан суд Париса следующим образом. Богини Гера, Афродита и Афина пришли к Парису, чтобы он решил, кто из них прекраснее. Богини обозначим их a, b, c высказали следующие утверждения. Парис предположил, что высказывания прекраснейшей из богинь истинны, а все утверждения двух остальных ложны. Мог ли Парис вынести свое решение? Кто прекраснейшая из богинь? Какие богини скрываются под именами а, b, c? Перед началом бегов на ипподроме четверо знатоков из числа зрителей обсуждали шансы трех фаворитов: Во время обсуждения были высказаны следующие утверждения. После заезда выяснилось, что фавориты А, В и С действительно заняли первые три места и что все четыре высказывания знатоков оказались истинными. Как фавориты поделили между собой места? Одинокий путник заблудился в лабиринте и попал в комнату, из которой можно выйти в одну из четырех дверей: X, Y, ZK W. По крайней мере одна из дверей ведет к выходу из лабиринта. Того, кто выходит через другую дверь, ожидает дракон, живущий в лабиринте. К удивлению путника в комнате находятся восемь жрецов, каждый из которых либо рыцарь и говорит всегда только правду, либо лжец и всегда лжет: Нашему путнику жрецы сообщили следующее:. Обвинитель на острове рыцарей и лжецов. На одном из островов, населенных рыцарями и лжецами, за совершение преступления судили двух местных жителей X и Y. Об обвинителе было известно, что он либо рыцарь, либо лжец. На суде обвинитель сделал два заявления:. Предположим, что некоторый человек, который может быть либо рыцарем, либо лжецом, делает следующие заявления:. Интервью на острове рыцарей и лжецов. У трех обитателей А, В и С острова рыцарей и лжецов взяли интервью, в ходе которого они высказали следующие утверждения:. Путешественник ищет остров с названием Майя. Исследуя третий остров, путешественник встретил двух жителей А и В, которые заявили следующее:. Исследуя шестой остров, путешественник встретил двух жителей А и В, которые заявили следующее:. Главная Статьи Новости Файлы Исходники Опросы Форумы Хостинг Eng Архив Карта. Поиск среди 20 статей: Конъюнктивная нормальная форма заданной пользователем формулы.
Какие витамины нужны против выпадения волос
Декоративный водоем с водопадом своими руками
Фильм 3 в скачать торрент
Маска глина лореаль
Сделать светильник в баню
Шугаринг в домашних условиях славянка спб