koi
mac
|
|||
|
|
||
|
|
win koi mac |
||
 |
| Главная | Форумы | Консультации | Конференции и круглые столы | Глоссарий | Участники проекта | Регистрация |
|
 | ||
|
1.01.1994 | РУДН/ ред. В.В.Ванчугов Мухачев В. П. "Нормальные формы формул логики высказываний и их применение при решении логических задач". Методические указания для студентов гуманитарных факультетов.САНКТ ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ В.П. МУХАЧЁ В Нормальные формы формул логики высказывани й и их применение при решении логических зада ч Методические указани я для студентов гуманитарных факультето в Санкт- Петербур г 200 0 Утверждены на заседании кафедры логики философского факультет а в качестве методических указаний 24 февраля 2000 г., прото кол 2 Утверждены и рекомендованы к изданию на заседани и редакционно-издательского совета 29 февраля 2000 г . Составитель: канд. филос. наук, доц. В.П. Мухач& #1105;в Рецензент: докт. филос. наук, проф. Б.И. Федоров Методические указания предназначены для студентов гу манитарных факультетов университетов. Они направлены на оказание им помощи в освоени и учебного материала по специальному курсу "Нормальные формулы формул логики выск азываний и их применение при решении логических задач", а также будут являться хороши м пособием к учебнику "Формальная логика" (Л., 1977). Особое внимание в методических указаниях уделяется применению нормальных форм для автоматического решения логических задач при помощи ЭВМ, ис пользующих программу "Метафора", созданную Ю.В. Нечита йловым. СОД ЕРЖАНИЕ Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 I. Логика высказываний . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Высказывания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Язык логики высказываний . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3 Семантика логических знаков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 4 Перевод суждений с естественного языка на язык логики высказываний . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 5 Таблицы формул логики высказываний . . . . . . . . . . . . . . . . . . . 7 6 Равносильные формулы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 7 Правило равносильной замены . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 8 Полные системы логических знаков . . . . . . . . . . . . . . . . . . . . . . . . . 11 9 Закон двойственности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 10 Тождественно-исти нные и тождественно-ложные формулы . . . . . . . . . . . . . . . . . . . . . . . . . 11 II. Нормальные формы формул логики высказываний ;. . . . . . . . . . . . . . . . . . . 12 11 Нормальная форма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 12 Проблема разрешения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 13 Конъюнктивная нормальная форма . . . . . . . . . . . . . . . . . . . . . . . . 14 14 Логическое следование и логические следствия . . . . . . . . . . . . 16 15 Сокращенная конъюнктивная нормальная форма . . . . . . . . . . . . . 16 16 Дизъюнктивная нормальная форма . . . . . . . . . . . . . . . . . . . . . . . . 17 17 Сокращенная дизъюнктивная нормальная форма . . . . . . . . . . . . . 18 III Автоматическое решение логических задач . . . . . . . . . . . . . . . . . . . . . . . . . 20 Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 НОРМАЛЬНЫЕ ФОРМЫ ФОРМУЛ ЛОГИКИ ВЫСКАЗ ЫВАНИЙ И ИХ ПРИМЕНЕНИЕ ПРИ РЕШЕНИИ ЛОГИЧЕСКИ Х ЗАДАЧ В ведение В данных методических указаниях рассматривается вопрос о применении нормальных форм при решении логических задач. Для того чтобы уметь реш ать данные задачи необходимо изучить искусственный язык логики высказываний и семантику логических знаков. Особое значение приобретает понятие равносильной замены, которая позволяет проводить тождественные преобразования формул лишь на основе синтаксическ их правил, не обращаясь к семантической интерпретации этих ф ормул. Нормальная форма является ключевым понятием данного курса. Приведение формул к нормальной форме дает возможность сформулировать процедуры, п озволяющие по внешнему виду формул давать их содержательную интерпретацию, а это в св ою очередь открывает путь к автоматическому решению логических задач. I. Логика выска зываний 1. Выска зывания Высказыванием называют предложение, выражающее суждение. Если суждение, составляющее предложение (смысл) некоторого высказывания, ис тинно, то о данном высказывании говорят, что оно истинно. Сходным образом ложным называют такое высказывание, которое является выражением ложного суж дения. Например, предложения: Искусственный логический язык не содержит омо нимических выражений; "Категории"- написаны Аристотелем; Если некоторое число являетс я простым, то оно делится только на себя и на единицу; являются истинными выска зываниями; а предложение: Число 6 является простым является ложным высказыв анием. Будем считать, что а) всякое высказывание истинно или ложно и б) ни одно высказывание не является сразу истинным или ложным. Истинность и ложность называют логическими, или истиннос тными, значениями высказываний. Если высказывание истинно, то говорят, что оно имеет логическое значение истина, а если высказывание ложно, то оно имеет логическое значени е ложь. Слова: не; неверно, что; и; или; если, то; тогда и тол ько тогда, когда; либо,либо; несовместно; ни,ни; не,но; но, не и их ближайшие синоним ы называют логическими союзами (знаками). Слова для всех, имеет место, что; для некоторых имеет место, что и их ближайшие синонимы называют кванторами. Логиче ские союзы и кванторы называют логическими постоянными. Логика занимается уст ановлением точного смысла этих слов и общих законов их употре бления. Высказывания, не содержащие логических постоянных, называют эле ментарными высказываниями. Ими являются, например, следующие предл ожения: (а) Имя есть звукосочетание с установленным зна чением; (б) "Не-человек" не ес ть имя; (в) 5 бо льше 7. Элементарные высказывания (а) и (б) имеют логическо е значение истина, (в) логическое значени е ложь. Высказывания, которые содержат логические постоянные , называют сложными высказываниями. Например, сложное высказывание Но не в сякая речь есть высказывающая речь, а лишь та, в которой содержится истинность ил и ложность чего-либо образовано с помощью союзов "но не" и "а". Сложные высказывания тоже истинны или ложны. Логическо е значение сложного высказывания зависит от логического значения высказываний, вход ящих в его состав и тех логических постоянных, с помощью которых оно пос троено. 2. Язык логики выска зываний Язык логики высказываний это искусственный язык, предн азначенный для анализа логической структуры сложных высказ ываний. Алфавит языка логики высказываний содержит три категории знаков: 1. Пропозициональные буквы (пропозициональные пе ременные): p, q, r, s, t, p1, q1, r1, s1, t1, p2, q2</S UB>, . 2. Логические знаки (логические союзы): &# 216; - знак отрицания (союз "не"); & - знак конъюнкции (сою з "и"); &# 218; - знак дизъюнкции (союз "или"); &# 201; - знак импликации (союз "если , то"); ≡ - знак эквивалентности (союз "тогда и только тогда, когда); ≠ - знак строгой дизъюнкции (союз "либо, либо). 3. Технические знаки: ( - левая скобка; ) правая скобка. Никаких других логических знаков в языке логики высказыван ий нет. Роль структурных образований, аналогичных элементарным и сложным высказываниям, играют в этом языке формулы. Формулы это таки е конечные последовательности знаков алфавита, которые построены по определенны м правилам и образуют законченные выражения языка логики высказ ываний. Определение формулы логики высказыван ий :
Никаких других формул, кроме указанных в п.п. 1) 3 ), в языке логики высказыван ий нет. Заглавные латинские буквы А и В, которые упо требляются в определении формулы, принадлежат не языку логики высказываний, а мета языку, т.е. тому языку, на котором мы говорим о языке логики высказываний, и служат для обозначения произвольных формул, записанных на языке логики высказываний. В отличие от букв, которые являются пропозициональными переменными, их называют метапереме нными, или метабуквами. Содержащие метабуквы выражения &# 216;А, (A&B), (A&# 218;B), (A&# 201;B), (A≡B), (A≠B) не формулы, а схемы формул определен ного вида. Например, выражение (A&B) есть схема формул (p&q), ((p&# 201;q)&(s≡t)), (p&(p&# 218;q)), (p&p) и т.п., а выражение (A&# 218;A) схема формул (p&# 218;p), (&# 216;q&# 218;&# 216;q) и ((p&# 201;r)&(p&# 201;r)), но не схема формулы (p&# 218;q). В дальнейшем мы часто будем говорить "формула (A&B)", подразум евая любую формулу логики высказываний соответствующего вида, а не саму запись (A&B ), которая является схемой формул. Относительно любой последовательности знаков алфавита яз ыка логики высказываний можно решить является ли она формулой или нет. Если эта последов ательность может быть построена в соответствии с п.п. 1)-3) определения формулы, то он а формула, еcли нет, то не формула. Заметим, что при построении формулы скобки п орождаются только знаками &, &# 218;, &# 201;, ≡, ≠; знак &# 216; скобок не порождает, т.е. выражение &# 216;А в скобки не берется, отдельная переменная также в скобки не б ерется. Схему построения формулы можно представить в виде фигур ы, которую называют деревом формулы. Например, дерево формулы ((&# 216;p&# 201;(q&r))≡(s&# 218;t)) име ет вид:
Подформулой данной формулы называется любая част ь формулы, которая сама есть ф ормула. Главным логическим знаком данной формулы называется логический знак, который при построении формулы применяется последним. Например, глав ным знаком формулы ((&# 216;p&# 201;(q&r))≡(s&# 218;t)) является знак ≡ и схему этой формулы можно представить в виде (А ≡В), где А обозначает подформулу (&# 216;p&# 201;(q&r)), а В подформулу (s&# 218;t). В свою очередь, главным логическим знаком выражения (&# 216;p&# 201;(q&r)) является знак &# 201; и, следовательно, эту формулу можно представить в виде (C&# 201;D), где С обозначает подформулу &# 216;p, а D подформулу - (q&r) и т.д. Кроме этого, мы будем считать пр оизвольную формулу собственной подфо рмулой. 3. Семантика логических знаков Знак отрицания (&# 216;) используется для обозначения на языке логики высказываний выражений вид а: "не-А", "А неверно", "А ложно", "А не может быть", и т.п. Высказывание &# 216;А истинно, когда ложно А, и ложно, когда ист инно А. Знак конъюнкции (&) используется для обозначения выражений вида "А и В", "А, но и В также", "А вместе с В", "А несмотря на В", "не только А, но и В", "Как А, так и В", "А, хотя и В" и т.п. Высказывание (A&B) истинно в том и только в том слу чае, когда истинно как А, так и В, и ложно во всех остальных с лучаях. Знак импликации (&# 201;) служит для обозначения выражений вида: "Если А, то В", "из А следует В", "А д остаточное условие для В", "В необходимое условие для А", "А, только если В", "В, е сли А", "А е сть В". Высказывание (А&# 201;В) ложно тогда и только тогда, когда формула А истинна, а формула В ложна, и истинна, если А ложна, или если формула В и стинна. Знак эквивалентности (≡) служит для обозначения выражений вида: "А тогда и только тогда, когда В", "А эквивалентно В", "А необходимое и д остаточное условие для В", "Если А, то и В, и наоборот", и т.п. Высказывание (А≡В) истинно, если истинностные значения А и В совпадают, и ложно, если их истинностные значения ра зличны. Знак строгой дизъюнкции(≠) служит для обозначения выражений вида: "либо А, либо В", "А и В несовместимы" и т.п. Высказывание (А≠В) истинно, если истинностные значения А и В различны, и ложно, если их истинностные значения сов падают. Таблицы ист инности Способы вычисления истинностных значений высказыв аний &# 216;А, (A&B), (A&# 218;B), (A&# 201;B), (A≡B), (A≠B) можно резюмировать следующими таб лицами.
4. Перевод суждений с естественного языка на язык логики выска зываний Построив искусственный логический язык, постоянным котор ого придан точный смысл, мы можем теперь переводить на него выражения естественного язык а. Перевод с разговорного языка на язык логики высказываний осуществляется в результате содер жательного анализа смысла предл ожений. Заметим, что формальной процедуры перехода от высказываний к формулам нет. Это связано с тем, что в естественных языках нет однозначного соответс твия между смыслами и способом его изложения. Мы можем предложить в качестве проц едуры лишь определенную последовательность шагов: 1) определяем все элементарные высказывания, которы е входят в состав данного сложного высказывания, и различным элементарным высказываниям поставляем различные пропозициональные пере менные; 2) определяем логические постоянные, с помощью которых построено данное сложное высказ ывание; 3) анализируя порядок, в котором данное сложное высказывани е строится из элементарных высказываний, записываем соответствующую ему ф ормулу. 5. Таблицы формул логики выска зываний Зная логические значения элементарных высказываний, мы можем с помощью одних только таблиц для, соответствующих логических союзов, уст анавливать логическое значение построенного из них сложного высказ ывания. По каждой формуле логики высказываний всегда можно построить отвечающую ей таблицу, в которой зафиксировано, какие логические значения будет получ ать данная формула при различных наборах логических значений переменных. Таблицу форм улы строят следующим о бразом: 1) Составляем список пропозициональных переменных , входящих в данную формулу (переменные выписываются без повто рений); 2) для каждой переменной строим соответствующий ей входной ( начальный) столбец т аблицы; 3) в каждой строке входных столбцов выписываем некоторы й отличный от остальных набор логических значений для всех пропозициональных перемен ных (число различных наборов логических значений n переменных, равно 2n< /SUP>); 4) в последовательности, определяемой порядком построе ния данной формулы из ее подформул, для каждой подформулы, которая отлична от переменн ой, строим соответствующий ей столбец т аблицы; 5) последний столбец, который называют заключительным ( выходным), соответствует данной ф ормуле; Заполнение этих столбцов логическими значениями осущ ествляется на основе приведенных выше таблиц для логических знаков: &# 216;, &, &# 218;, &# 201;, ≡, & #8800;. Построим таблицу для формулы (&# 216;p &# 201; (q &# 218; r)).
Из таблицы видно, что данная формула истина для семи наборов логических значений своих переменных и ложна только для одного, когда переменные p, q и r принимают логическое значени е ложь. 6. Равносильные формулы Иногда различные по своей структуре формулы таковы, что одинаковым наборам логических значений переменных во входных столбцах таблиц этих форму л отвечают одинаковые логические значения в соответствующих строках заключительных ст олбцов. Например, в таблицах формул (p&# 201;q) и (&# 216;p&# 218;</F ONT>q)
одинаковым наборам логически х значений переменных p и q во входных столбцах отвечают одинаковые логические значения в соотв етствующих заключительных столбцах. О подобных формулах говорят, что они равно сильны. Определение. Пусть А и В формулы. Е1, Е2,, Еn список всех пропозициональных переменных, входящих по кр айней мере в одну из них. Будем говорить, что А и В равносильные формулы ( и писат ь: А и В), если при любых логических значениях Е1, Е2,, Еn логические значения А и В сов падают. Равносильными, следовательно, могут быть не только таки е формулы, в которые входят не только одни и те же пропозициональные переменные, н о и такие, в которые входят разные пере менные. Говорят, что логические значения формулы А не зависят от пропози циональной переменной Еi, если для любого набора логических значений остальных пропози циональных переменных в таблице формулы А логическое значение А одно и то же, когда Еi истинно и когда Еi ложно. Отношение равносильности, во-первых, рефлек сивно, т.е. А равносильно А; во-вторых, симметрично, т.е. если А равноси льно В, то В равносильно А, и в третьих, транзитивно, т.е. если А равносильно В и В р авносильно С, то А равноси льно С. Два высказывания называются равнозначными, если они могут быть получены из равносильных формул А и В в результате замены всех вход ящих в них переменных конкретными высказыв аниями. Приведем список некоторых равносильных формул, условившись в дальнейшем во всех формулах для упрощения записи опускать внешние скобки:
7. Правило равносильной замены Используя транзитивность отношения равносильности, мы, зная о равносильности одних формул, можем судить о равносильности других. Имеет место следующая те орема. Теорема. Пусть АВ обозначает формулу А с выделенным вхождением подформулы В, а AB формулу, которая получается из А заменой выделенного вхождения В в А на формулу В'. Тогда если В равносильно В', то АВ равносильно АВ . Правило, разрешающее в формуле А выделенное вхождение подформулы В заменять равносильной формулой В, называется правилом равносильной заме ны. Это правило позволяет, опираясь на равносильность од них формул (В и В), устанавливать равносильность других (А и А). Равносильности (1) (24) были обоснованы с помощью таблиц. Теперь с помощью этих равносильностей, пользуяс ь правилом замены, мы можем установить равносильность формул уже без обращения к та блицам. Пусть, например, дана формула &# 216;(p&q)&# 201;</F ONT>r. Заменяем, согласно равносильности (12) подформулу эт ой формулы &# 216;(p&q) равносильной ей формулой (&# 216;p&# 218;&# 216;q). В результате получаем формулу (&# 216;p&# 218;&# 216;q)&# 201;</F ONT>r. Далее, так как каждая формула рассматривается в качестве подформулы самой себя, то заменяем согласно равносильности (15) формулу (&# 216;p&# 218;&# 216;q)&# 201;r формулой &# 216;(&# 216;p&# 218;&# 216;q)&# 218;</F ONT>r. Таким образом, полученная формула, в силу транзитивности отношения равносильности, равносильна исходной формуле &# 216;(p&q)&# 201;</F ONT>r. 8 и 9. Полные системы логических знаков и Закон двойств енности В этих параграфах учебника "Формальная логика" рассм атривается семантическая взаимосвязь логических союзов. Особое внимание следует о братить на сводимость полной системы логических знаков лишь к некоторым из них. А также на симм етричность знаков & и &# 218;, ≡ и & #8800;. 10. Тождественно-истинные и тождественно-ложные формулы Существуют формулы, которые при любых наборах логически х значений переменных получают в заключительном столбце таблицы логическое значение "истина". Такие формулы называют тождественно-истинными формулами или л огическими тождествами. Например, таковыми является формулы p&# 201;p и p&# 218;&# 216;p. Каждая тождественно-истинная формула выражает какой-то логический закон. Формула p&# 201;p есть известный логический закон тождества, а формула p&# 218;&# 216;p - закон исключенного третьего. Все тождественно-истинные формулы р авносильны друг другу. Существуют также формулы, которые при любых наборах логических значений переменных получают в заключительном столбце своей таблицы логическо е значение "ложь". Они называются тождественно-ложными (противоречивыми) формулам и. Таковой является, например, формула p&&# 216;p. Все тождественно-ложные формулы равносильны друг другу. Если мы обозначим заглавной буквой И формулу, котора я является тождественно-истинной, а заглавной буквой Л тождественно-ложную формулу , и буквой А произвольную формулу, то будут иметь место следующие равносил ьности: &# 216;И равноси льно Л; &# 216;Л равноси льно И; А≡И равноси льно А; А≡Л равносильно &# 216;</F ONT>А; А&И равноси льно А; И&А равноси льно А; А&Л равноси льно Л; Л&А равноси льно Л; А&# 218;И равноси льно И; И&# 218;А равноси льно И; А&# 218;Л равноси льно А; Л&# 218;А равноси льно А; Знание о том, что какие-то формулы тождественно-истинны, позволяет судить о тождественной истинности других формул. Имеют место следующие т еорем ы .
II. Нормальные формы формул логики выска зываний 11. Нормальна я форма Определение: формула логики высказываний имеет нормаль ную форму, ес ли она: а) не содержит знаков &# 201;, ≡, & #8800;; б) знаки отрицания стоят в ней только при пере менных. Любую формулу А, не имеющую нормальной формы, можн о конечным числом применений правила замены преобразовать в формулу А`, которая имеет нормальную форму. Процесс такого преобразования будем называть процессом приведен ия формулы к нормальной форме. Для того чтобы данную формулу привести к нормаль ной форме, необходимо произвести в ней следующие равносильные замены, используя ра вносильные формул ы из 6: 1) каждую подформулу вида (А≠В) заменить согласно равн осильности (19) формулой (А&# 218;В)&(&# 216;A&# 218;&# 216;</FO NT>B); 2) каждую подформулу вида (А≡В) заменить согласно равн осильности (18) формулой (&# 216;А&# 218;В)&(&# 216;В&# 218;</FO NT>А); 3) каждую подформулу вида (А&# 201;В) заменить согласно равносильности (15) формулой (&# 216;А&# 218;</FO NT>В); 4) каждую подформулу вида &# 216;(А&В) заменить согласно равносильности (12) формулой (&# 216;А&# 218;&# 216;</FO NT>В); 5) каждую подформулу вида &# 216;(А&# 218;В) заменить согласно равносильности (13) формулой (&# 216;А&&# 216;</FO NT>В); 6) каждую подформулу вида &# 216;&# 216;А заменить согласно равносильности (1) формулой& nbsp;А. Формула имеет нормальную форму, если ни один из пер ечисленных пп. 1)-6) настоящего предписания к ней не пр именим. Пусть, например, дана формула &# 216;(p ≡ &# 216;</FO NT>q). Согласно равносильности (18) получаем формулу &# 216;((&# 216;p &# 218; &# 216;q)&(&# 216;&# 216;q&# 218;</FON T>p)). Из нее согласно равносильности (12) получаем фор мулу &# 216;(&# 216;p &# 218; &# 216;q)&# 218;&# 216;(&# 216;&# 216;q&# 218;</FO NT>p), затем согласно равносильности (1) формулу &# 216;(&# 216;p &# 218; &# 216;q)&# 218;&# 216;(q&# 218;</FO NT>p), и далее, согласно равносильности (13) получаем форм улу (&# 216;&# 216;p & &# 216;&# 216;q)&# 218; (&# 216;q&&# 216;</FO NT>p), и, наконец, согласно равносильности (1) получаем формул у (p & q)&# 218; (&# 216;q&&# 216;</FO NT>p), которая имеет нормальную форму. 12. Проблема раз решения Каждая формула логики высказываний принадлежит одному из следующих трех кл ассов: 1) истинных при любых логических значениях своих переменных (то ждественно -истинные формул ы); 2) ложных при любых логических значениях своих переменных (тождестве нно-ложные фо рмулы); 3) истинных при одних значениях переменных и ложных при других (нейтральные формул ы). Формула логики высказываний называется выполнимой фор мулой, если хотя бы для одного набора логических значений своих переменных он а получает значение "истина". Таким образом, тождественно-истинные и нейтральные формул ы являются выполнимыми, а тождественно-ложные формулы не выпол нимыми. Задача, состоящая в отыскании процедуры, позволяющей для любой формулы выяснить: какому из трех перечисленных выше классов она принадлежит, называется семантической проблемой разрешения для формул логики высказываний. В со ответствии с этим процедура, позволяющим конечным числом простых действий решить проблему разрешения называется разрешающей процедурой. Ясно, что процесс построения по данной формуле отвечающей ей таблице есть разрешающая процедура семантической проблемы разрешения для формул логики высказ ываний. Однако использовать процесс построения таблицы в качестве р азрешающей процедуры семантической проблемы разрешения практически удобно лишь в те х случаях, когда в формулу входит лишь небольшое число переменных и она не очень длинна я. Следует учитывать, что число строк в таблице быстро растет с увеличением числа входящих в формулу переменных. Стремясь избежать построения громоздких таблиц, ищ ут другие, более удобные, разрешающие про цедуры. Заметим, что для того чтобы получить разрешающую процедуру, достаточно найти способ, позволяющий отличить тождественно-истинные формулы от всех остальных. В самом деле, если в результате применения такой процедуры к формуле А в ыясняется, что она тождественно-истинна, то проблема разрешения решена. Если же в ыясняется, что она не тождественно-истинна, то данную процедуру нужно применить к фор мулу &# 216;А. Если в результате ее применения к &# 216;А, выяснится, что &# 216;А тождественноистинная формула, то значит, формула А тождественноложна. Есл и же &# 216;А так же как А не тождественноистинна, - значит, формула А нейтральная , т.е. при одних значениях переменных она - истинна, а при других - ложна. В следующих параграфах мы опишем формальные процедуры, с помощью которых для любых формул логики высказываний, не прибегая к построению таб лиц, можно решить вопрос, тождественноистинна данные формулы и ли нет. 13. Конъюнктивная нормальна я форма Выше уже было замечено, что для того чтобы получить р азрешающую процедуру, достаточно найти способ, позволяющий отличить тождественно-истинн ые формулы от всех остальных. Следовательно, чтобы найти указанный способ нам необходим о ответить на следующий вопрос: можно ли установить какую-нибудь закономерную с вязь между структурой формулы и ее семантикой, между ее логической формой и логическим со держанием? Оказывается, что такая связь существует и можно указать простой метод, п озволяющий по виду формулы, приведенной к некоторой стандартной форме, судить о том, тождествен ноистинная данная формула и ли нет. Назовем элементарной дизъюнкцией формулу, кот орая име ет вид А1&# 218;А2&# 218;&# 218;Аn , где n ≥ 1, а Аi (i ≤ n) есть либо п еременная, либо отрицание переменной. Например, формула p&# 218;q&# 218;&# 216;r&# 218;p&# 216;q&# 218;r - элементарная дизъ юнкция. Теорема. Элементарная дизъюнкция тождественно - ист инна тогда и только тогда, когда в ней содержится хотя бы одна пара дизъюнктивных членов, из которых один есть некоторая переменная, другой ее отр ицание. Определение. Формула логики высказываний имеет кон ъюнктивную нормальную форму (КНФ), если она име ет вид: B1 & B2 & & Bm , где B1, B2, , Bm, - элементарные дизъюнкции и m ≥ 1. Например, формула p & (&# 216;q &# 218; r) & &# 216;s & (&# 216;p &# 218; &# 216;</F ONT>r) имеет конъюнктивную нормальную форму. Любая формула логики высказываний в результате ряда ра вносильных замен может быть приведена к конъюнктивной нормальной форме. Формулу, ра вносильную данной и имеющую конъюнктивную нормальную форму. будем называть кон ъюнктивной нормальной формой данной ф ормулы. Для того чтобы формулу привести к КНФ, необходим о в начале с помощью известной процедуры привести ее к нормальной форме. Затем каждую подформулу вида (А&# 218;(В&C)) согласно равносильности (6) и каждую подформулу вида ((B&a mp;C)&# 218;A) согласно равносильности (7) заменить формулой ((A&# 218;B)&(A&# 218;C)). Формула имеет КНФ, если она имеет нормальную форму и в ней нет подф ормул вида (А&# 218;(В&C)) и ((B&C)&# 218;</FO NT>A). Формула, имеющая КНФ, тождественна-истинна тогда и тол ько тогда, когда тождественноистинны все ее конъюнктивные члены, т.е. когда каждая эл ементарная дизъюнкция содержит хотя бы одну пару дизъюнктов, из которых один есть некоторая переменная, а другойее отр ицание. Пусть дана формула (p&# 201;q)&# 201;(&# 216;q&# 201;&# 216;</FO NT>p). Приведем ее к КНФ: &# 216;(&# 216;p&# 218;q)&# 218;(&# 216;&# 216;q&# 218;&# 216;</FO NT>p); (&# 216;&# 216;p&&# 216;q)&# 218;(q&# 218;&# 216;</FO NT>p); (p&&# 216;q)&# 218;(q&# 218;&# 216;</FO NT>p); (p&# 218;q&# 218;&# 216;p)&(&# 216;q&# 218;q&# 218;&# 216;</FO NT>p). Можно видеть, что все конъюнктивные члены КНФ данной формул ы содержат некоторую переменную одновременно со знаком отрицания и без него. След овательно, данная формула тождественноис тинная. Каждая не тождественноистинная формула имеет КНФ, которая называется совершенной. Процедуру приведения к совершенной КНФ можно взять в учебник е, мы лишь заметим, что с помощью этой процедуры можно определить все возможные сл едствия из некоторого списка п осылок. 14. Логическое следование и логические сл едствия Пусть А1, А2, , Аn и В формулы , а Е1, Е2, , Еm совокупность всех пропози циональных переменных, входящих по крайней мере в одну из них. Будем говорить, что формула В логически следует из формул А1, А2, , Аn, если при всех тех логических значениях Е1, Е2, , Еm при которых формулы А1, А2, , Аn истинны , она тоже и стинна. Для того чтобы проверить, выполняется ли это условие, нужно выяснить, может ли формула (А1 & А2 & & Аn</S UB>) &# 201; В, хотя бы при одном наборе логических значений переменных Е1, Е2, , Еm, быть ложной. Если эта формула тождественноистинна, то не существует такого набора логических значений ее переменных, при котором подформулы А1, А2, , Аn истинны, а подформула В логически след ует из формул А1, А2, , Аn, если тождественноистин на формула (А1 & А2 & & Аn) &# 201;</FO NT> В. Формула В называется в этом случае логическим след ствием (заключением) формул А1, А2, , Аn, а формулы А1, А2, , Аn называются посылками фор мулы В. Используя в качестве разрешающей процедуры процесс приведения формул к КНФ, можно для любой формулы В и любого списка формул А1, А2, , Аn решить логическую задачу: является ли В логическим следствием со вокупности посылок и ли нет? Процедуру приведения формулы к совершенной КНФ испо льзуют для решения задачи отыскания логических следствий данных посылок, т.е. эта процедура является методом систематического обзора следствий из любого числа п осылок. 15. Сокращенная конъюнктивная нормальна я форма С помощью совершенной КНФ можно получить обзор всех следствий из данных посылок, однако нас обычно интересуют лишь наиболее сильные сле дствия данных посылок. С этой точки зрения представляют интерес так называемые простые следствия. Следствие В из посылок А1, А2, , Аn называют простым, если В есть такая не содержащая повторений и не тождественн о-истинная элементарная дизъюнкция, которая не "поглощается" (в смысле "закона пог лощения" - равносильности (21)) никаким другим более сильным следствием из посылок А1, А2, , Аn того же вида. Простые следствия из данн ых посылок можно найти, приводя их конъюнкцию к сокращенн ой КНФ. Определение. Сокращенной КНФ данной формулы называетс я такая ее КНФ, которая удовлетворяет следующим ус ловиям: 1) ни в одном конъюнктивном члене нет двух одинаковых дизъ юнктов; 2) ни в одном конъюнктивном члене нет таких двух одинаковых дизъюнктов, из которых один есть переменная, а другой отрицание этой пере менной; 3) нет таких пар конъюнктивных членов, что каждый д изъюнкт из одного имеется в другом, т.е., во-первых, нет двух одинаковых конъюнктивн ых членов, а во-вторых, нет таких двух конъюнктивных членов, из которых один поглощается другим; 4) если имеются такие два конъюнктивных члена, из ко торых один содержит некоторую переменную, а другой ее отрицание (при условии, что другой п еременной, для которой это же имеет место, в данных конъюнктах нет), то в той же К НФ имеется конъюнктивный член, который является элементарной дизъюнкцией, построенн ой из всех дизъюнктов данной пары, отличной от упомянутой переменной и ее отр ицания. Для того чтобы привести формулу к сокращенной КНФ необ ходимо: 1) привести ее к КНФ; 2) из всех одинаковых конъюнктивных членов КНФ остав ить только один и в элементарных дизъюнкциях также устранить все повт орения; 3) устранить все тождественноистинные конъюнктивные члены; 4) если необходимо (см. определение сокращенной КНФ), то на основании закона выявления применить равносильность (23). В качестве законов выявлени я мы будем также использовать равносильности: (23a) C&(B&# 218;&# 216;C) равносильно C&(B&# 218;&# 216;C)& amp;B и (23b) (A&# 218;C)&&# 216;C равносильно (A&# 218;C)&&# 216;C &A. 5) если в новых (добавленных) конъюнктивных членах К НФ имеются повторения, то устран ить их; 6) применить, если это возможно, закон поглощения, т.е. равн осильность (24). Формула, получившаяся в результате применения пп.1) - 6), имеет сокращенную конъюнктивную нормальную форму и каждый ее конъюнкт есть простое следствие исходной ф ормулы. 16. Дизъюнктивная нормальна я форма Формулы логики высказываний наряду с КНФ могут иметь диз ъюнктивную нормальную форму (ДНФ). Условимся называть элементарной конъюнкцией формулу, которая име ет вид: A1 & A2 && An , где n ≥ 1, a Ai (i ≤ n) либо п еременная, либо отрицание переменной. Например, ф ормула p & q & &# 216;r & p & &# 216;q & r - элементарная конъюнкция, а формула (p &# 218; q) & r & p элементарной конъюнкцией не является, так как ее первый кон ъюнктивный член не есть переменная, ни отрицание этой пере менной. Теорема. Элементарная конъюнкция тождестве нно ложна тогда и только тогда, когда в нее входит хотя бы одна пара конъюнктивн ых членов, из которых один есть некоторая переменная, а другой ее отр ицание. Определение. Формула логики высказываний имеет диз ъюнктивную нормальную форму, если она имеет вид В1 &# 218; В2 &# 218; &# 218; Вm, где В1, В2 Вm, - эл ементарные конъюнкции и m 805; 1. Например, формула p &# 218; (&# 216;q & r) &# 218; &# 216;s &# 218; (&# 216;p & &# 216;r) имеет дизъюнктивную нормальную форму. Любая формула логики высказываний в результате ряда ра вносильных замен может быть приведена к дизъюнктивной нормальной форме. Формулу, ра вносильную данной и имеющую дизъюнктивную нормальную форму, будем называть диз ъюнктивной нормальной формой данной ф ормулы. Для того чтобы привести формулу к ДНФ необходимо вначал е привести ее к нормальной форме. Затем каждую подформулу вида (A&(B&# 218;C)) согласно равносильности (8) и каждую подформулу вида ((В&# 218;С)&A) согласно равносильности (9) заменить формулой ((A&B)&# 218;(A&am p;C)). 17 Сокращенная дизъюнктивная нормальна я форма Гипотезой формулы В называют такую формулу А, ч то формула А&# 201;В тождественноистинна. Если А гипотеза формулы В, то А&C тоже гипоте за формулы В; если А и С гипотезы формулы В, то А&# 218;С тоже гипотеза В. Дизъюнктивные члены совершенной ДНФ (см. учебник) данн ой формулы есть различные гипотезы, при истинности которых данная формула и стинна. С помощью СДНФ можно получить обзор всех гипотез данно й формулы, которые имеют СДНФ. Но нас обычно интересуют лишь самые слабые гипот езы. С этой точки зрения представляют интерес так называемые простые гипотезы . Гипотеза А формулы В называется простой, если А есть элементарная конъюнкци я, которая не тождественноложна, не содержит повторений и не поглощается никакой дру гой, более слабой, гипотезой формулы В такого же вида. Простые гипотезы данной фор мулы можно найти, приводя ее к сокращенн ой ДНФ. Определение. Сокращенной ДНФ данной формулы называется такая ее ДНФ, которая удовлетворяет следующим ус ловиям: 1) ни в одном дизъюнктивном члене нет двух одинаковых конъ юнктов; 2) ни в одном дизъюнктивном члене нет таких двух одинаковых конъюнктов, из которых один есть переменная, а другой отрицание этой пере менной; 3) нет таких пар дизъюнктивных членов, что каждый к онъюнкт из одного имеется в другом; т.е., во-первых, нет двух одинаковых дизъюнктивн ых членов, а во - вторых, нет таких двух дизъюнктивных членов, из которых один поглощается другим; 4) если имеются два дизъюнктивных члена, из которых оди н содержит некоторую переменную, а другой ее отрицание (при условии, что другой переменной для которой это же имеет место, в данных дизъюнктах нет), то в этой же Д НФ имеется дизъюнктивный член, который является элементарной конъюнкцией, построенн ый из всех конъюнктов данной пары, отличных от упомянутой переменной и ее отр ицания. Для того чтобы привести формулу к сокращенной ДНФ нужно произвести следующие преобраз ования: 1) привести ее к ДНФ; 2) из всех одинаковых дизъюнктивных членов ДНФ остав ить только один и в элементарных дизъюнкциях тоже устранить все повт орения; 3) устранить из ДНФ все тождественно-ложные дизъюнктивные члены; 4) если необходимо, то на основании закона выявления применить равносильность (24). В качестве законов выявления мы будем также использовать равн осиль ности (24а) С&# 218;(В&&# 216;C) равносильно С&# 218;(В&&# 216;C)&# 218;В и (24b) (A&C)&# 218;&# 216;C равносильно (A&C)&# 218;&# 216;C&# 218;</F ONT>A, которые можно рассматривать как такие частные случаи равн осильности (24), в которых отсутствуют либо формула А, либо фор мула В; 5) если в новых дизъюнктивных членах ДНФ имеются повт орения, то устран ить их; 6) если среди дизъюнктивных членов ДНФ имеются таки е, которые поглощаются другими, то, применяя правило замены по равносильности (22), устранить все поглощаемые дизъюнктивные члены. Получившаяся в результате формула есть сокращенная ДНФ данной формулы, каждый дизъюнкт которой ее простая гипотеза. Таким образом, для того чтобы получить все простые гипотезы, то есть найти те самые слабые допущения, п ри которых данная формула была бы их следствием, нужно привести формулу к сокращенн ой ДНФ.
III. Автоматическое решение логически х задач С помощью нормальных форм можно решать следующие логические задачи: 1) является ли данная формула тождественно-истинной (КНФ); 2) следует ли данная формула В из посылок А1, А2, , Аn (КНФ); 3) выведение всех следствий из данных посылок (совершенна я КНФ); 4) выведение простых следствий из данных посылок (с окращенная КНФ); 5) является ли данная формула тождественно- ложной (ДНФ); 6) из каких гипотез следует данная формула (совершенна я ДНФ); 7) из каких простых гипотез следует данная формула (с окращенная ДНФ). Примеры решения этих задач можно найти в учебнике " Формальная логика", а автоматическое решение такого типа задач можно производить, используя программу "Метафора", созданную Ю.В. Нечитайловым. С данной программой можно оз накомиться на кафедре логики. Мы же рассмотрим применение нормальных форм для реше ния других типов задач, которые мы назовем задачами Р. Сма ллиана. Рассмотрим некоторые из задач Р. Смаллиана. Существует множество хитроумных задач об острове населенном "рыцарями", всегда говорящими правду, и "лжецами", изрекающими только ложь. Предполагается, что каждый обитатель острова ли бо рыцарь, либ о лжец. Задача 1. В этой задаче два персонажа А и В. Каж дый из них либо рыцарь, либо лжец. Персонаж А высказывает следующее утверждение: " По крайней мере один из нас лжец". Кто из двух персонажей А и В рыцарь, а кт о лжец? Переведем условие задачи на язык логики высказываний. Ут верждение, высказанное А "По крайней мере один из нас лжец" является сложным и озн ачает, что А может оказаться лжецом и В может быть лжецом, а также и т о, что они оба могут быть лжецами. Следовательно, в качестве логического союза мы вы берем знак &# 218; ("или" - знак). Теперь это утверждение будет иметь следующий вид: А: А лжец или В лжец. Обозначим утверждение "А рыцарь" формулой p. Утверждение "А лжец" - формулой &# 216;p (не рыцарь), это возможно, так как существует только два типа п ерсонажей. Утверждение "В рыцарь" обозначим формулой q, а утверждение "В- лжец" обозначим формулой &# 216; q. Теперь исходное утверждение, высказанное А будет иметь вид: А: &# 216;p &# 218; &# 216;</F ONT>q. Однако для решения задачи проведение этой формализации нед остаточно, поскольку она не дает ответа на вопрос задачи. Далее рассуждаем следующи м образом. Персонаж А может быть как рыцарем, так и лжецом, следовательно, его у тверждение может быть как истинным, так и ложным. Включаем этот факт в условие зад ачи. Тогда она будет име ть вид: 1) Если А рыцарь, то утверждение "По крайней мере о дин из нас лжец" будет ис тинным. 2) Если А лжец, то утверждение "По крайней ме ре один из нас лжец" будет ложным. Используя наши обозначения для утверждений типа "А рыцарь", "А лжец" и т.д., запишем полученные условия задачи на яз ыке логики высказ ываний: 1) p&# 201;(&# 216;p&# 218;&# 216;</FO NT>q); 2) &# 216;p&# 201;&# 216;(&# 216;p&# 218;&# 216;</FO NT>q). Соединяем оба условия конъю нкцией. (p&# 201;(&# 216;p&# 218;&# 216;q))& (&# 216;p&# 201;&# 216;(&# 216;p&# 218;&# 216;</FON T>q)). Теперь у нас есть полная формализация данной задачи и на м остается найти простые следствия из известных условий (посылок). Следовательно, нам необходимо применить сокращенн ую КНФ. (p&# 201;(&# 216;p&# 218;&# 216;q))& (&# 216;p&# 201;&# 216;(&# 216;p&# 218;&# 216;</FON T>q)); (&# 216;p&# 218;&# 216;p&# 218;&# 216;q)& (&# 216;&# 216;p&# 218;&# 216;(&# 216;p&# 218;&# 216;q)) равносильност ь (15); (&# 216;p&# 218;&# 216;p&# 218;&# 216;q)& (&# 216;&# 216;p&# 218;(&# 216;&# 216;p&&# 216;&# 216;q)) равносильност ь (13); (&# 216;p&# 218;&# 216;q)& (&# 216;&# 216;p&# 218;(&# 216;&# 216;p&&# 216;&# 216;q)) равносильност ь (11); (&# 216;p&# 218;&# 216;q)& (p&# 218;(p&q)) равносильнос ть (1); (&# 216;p&# 218;&# 216;q)& p равносильност ь (22); (&# 216;p&# 218;&# 216;q)& p&&# 216;q равносильность (23b); p&&# 216;q равносильност ь (21). Ответ: p означает, что А является рыцарем, а &# 216;q означает, что В является лжец ом. Задача 2. Предположим, что А говорит: "Или я лжец, или В рыцарь". Кто из двух персонажей А и В рыцарь, и кт о лжец? Сначала осуществляем перевод утверждения А на язык логики вы сказываний так, как мы это делали для первой задачи: А: &# 216;p &# 218;</FO NT> q. Далее, используя общие условия преобразуем утверждение А в следующи е два: 1) p &# 201; (&# 216;p &# 218;</FON T> q); 2) &# 216;p &# 201; &# 216;(&# 216;p &# 218;</FON T> q). Соединяем посылки конъюнкцией и приводим формулу к с окращенно й КНФ. (p &# 201; (&# 216;p &# 218; q)) & (&# 216;p &# 201; &# 216;(&# 216;p &# 218; q)); (&# 216;p &# 218; &# 216;p &# 218; q)) & (&# 216;&# 216;p &# 218; &# 216;(&# 216;p &# 218; q)) равносильност ь (15); (&# 216;p &# 218; &# 216;p &# 218; q)) & (&# 216;&# 216;p &# 218; (&# 216;&# 216;p & &# 216;q)) равносильност ь (16); (&# 216;p &# 218; q) & (&# 216;&# 216;p &# 218; (&# 216;&# 216;p & &# 216;q)) равносильност ь (11); (&# 216;p &# 218; q) & (p &# 218; (p & &# 216;q)) равносильнос ть (1); (&# 216;p &# 218; q) & p равносильност ь (21); (&# 216;p &# 218; q) & p&q - равносильность (23b); p&q - равносильност ь (21). Ответ: А и В рыцари. *** Метод решения задач 1 и 2 представляет собой пример фо рмализации задач о "Рыцарях и Лжецах". Он является частым случаем подхода к более общей проблеме, которую мы сформулируем следующим образом: можно ли для кажд ой хорошо сформулированной задачи найти алгоритм, преобразовывающий ее содержани е в форму, допускающую автоматическое решение этой задачи на ЭВМ? Понятие "хорошо сформулированная задача" характеризуется следующими приз наками: 1) задача должна быть сформулирована в рамках возм ожного мира с точно очерченной семантикой, например: задачи о "Рыцарях и Лжецах" име ют решение только в границах классической логики, для которой выполняются законы тожества, пр отиворечия и исключенного тр етьего; 2) объекты этого возможного мира обладают конечным числом с войств; 3) каждому свойству сопоставляется определенная операция, например: если некто является Лжецом, то все его утверждения записываются со знаком отр ицания. 4) совокупность этих операций составляет некоторую последов ательность действий, преобразующих содержание задачи в форму, к которой применимы чисто синт аксические преобразования (исчисления), например: для решения задач о "Рыцарях и Лжецах" ис пользуются нормальные формы; 5) существует формальный критерий правильного ответа, например: после приведения формулы к сокращенной КНФ все элементарные дизъюнкции д олжны быть представлены либо, некоторой переменной либо ее отри цанием; Пример построения ал горитма Пусть Xi произвольный персонаж задачи о "Рыцарях и Лжецах". Пусть Р символ обозначающий свойство быть рыцарем, &# 216;Р символ обозначающий свойство быть лжецом и S общий символ для обозначен ия рыцарей и лжецов. Тогда выражение: Р(Хi) обозначает рыцаря;
выражение &#
216;Р(Xi) обозначает лжеца, где ( Получение информации: некто S(Хi) утверждает I(Xi), где I(Xi) информация от I го участника о свойствах перс онажей. Поскольку для каждого персонажа заранее не известно я вляется он рыцарем или лжецом, то построение алгоритма состоит в семантическом ра зборе этих вар иантов: Р(Хi) &# 201; I(Xi) Рыцари всегда говорят правду. &# 216;Р(Xi) &# 201; &# 216;I(Xi) Лжецы всегда утверждаю т ложь. Далее, если дано: I(X1),, I(Xm), где m число высказавшихся участников, то исходное уравнение будет иметь следующ ий вид: (Р(Х1) &# 201; I(X1)) & (&# 216;Р(X1) &# 201; &# 216;I(X1))& & (Р(Хm) &# 201; I(Xm)) & (&# 216;Р(Xm) &# 201; &# 216;I(Xm</ SUB>)). Ответ на задачу должен быть получен, посредством приведе ния данной формулы к сокращенной КНФ, в виде S(X1) & S(Xn), где S(Xi) есть либо Р(Хi), либо &# 216;Р(Хi< /SUB>). Теперь, используя указанный алгоритм, решим еще одну задачу. Задача 3. Предположим, что А высказывает утверждение : "Я лжец, а В не лжец." Кто из персонажей рыцарь и кт о лжец? Переводим утверждение А на язык логики высказываний. Пусть при этом переменная p обозначает, что А-рыцарь, а переменная q о бозначает, что В-рыцарь. Утверждение А принимает тепе рь вид: A: &# 216;p & &# 216;&# 216;</F ONT>q. Или, применяя равносильность (1), по лучаем, A: &# 216;p & amp; q. Применяем основную формулу к информации, полученно й от А: (p &# 201; (&# 216;p & q)) & (&# 216;p &# 201; &# 216;(&# 216;p &am p; q)); Приводим эту формулу к сокращенн ой КНФ: (p &# 201; (&# 216;p & q)) & (&# 216;p &# 201; &# 216;(&# 216;p &am p; q)); (&# 216;p &# 218; (&# 216;p & q)) & (&# 216;&# 216;p &# 218; &# 216;(&# 216;p & q)) равносильност ь (15); (&# 216;p &# 218; (&# 216;p & q)) & (p &# 218; &# 216;(&# 216;p & q)) равносильнос ть (1); (&# 216;p &# 218; (&# 216;p & q)) & (p &# 218; (&# 216;&# 216;p &# 218; &# 216;q)) равносильность &# 216;(А& amp;B); (&# 216;p &# 218; (&# 216;p & q)) & (p &# 218; p &# 218; &# 216;q) - равносильнос ть (1); (&# 216;p &# 218; (&# 216;p & q)) & (p &# 218; &# 216;q) - равносильност ь (11); (&# 216;p &# 218; &# 216;p) &(&# 216;p &# 218; q) & (p &# 218; &# 216;q) - равносильнос ть (6); &# 216;p &(&# 216;p &# 218; q) & (p &# 218; &# 216;q) - равносильност ь (11); &# 216;p & (p &# 218; &# 216;q) - равносильност ь (21); &# 216;p & (p &# 218; &# 216;q) & &# 216;q- равносильность (23a); &# 216;p & &# 216;q- равносильност ь (21); Ответ: А и В лжецы. Для решения задач Р. Смаллиана (и не только его) удобно по льзоваться программой "Метафора", которую мы упоминали выше. Эта программа выполняе т операции по приведению формул к КНФ, сокращенной КНФ, ДНФ и сокращенной ДНФ. В о бязанности пользователя входит самостоятельный семантический анализ задачи и запи сь условия задачи по основной формуле указанного алгоритма. Если анализ проведен верно, то программа выдает правильный ответ. Если анализ не верен или условие задачи содерж ит ошибки, то программой будет выдан результат, по форме которого легко определяются выш еуказанные ошибки. Кроме задач о "Рыцарях и Лжецах" существует множество других логических задач, например, у того же Р.Смаллиана. Для каждого нового типа задач необходимо создавать новый алгоритм, но если семантический анализ задачи верен, то применение к нему нормальных форм обязательно приводит к получению правильного резу льтата. ЛИТЕ РАТУРА: Бродский И.Н. Элементарное введение в символическ ую логику. Л. , 1973. Смаллиан Р. Как же называется эта книга? М. , 1981. Смаллиан Р. Алиса в cтране cмекалки. М. , 1985. Смаллиан Р. Принцесса или тигр. М. , 1987. Формальная логика: Учебник / Под ред. И.Я.Чупахина и И.Н. Бродского. Л.: изд-во Ленингр. ун-т |
| Напишите нам | Авторам |
.
, где n число персо
нажей).