Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 3
Текст из файла (страница 3)
Тот удивляется — у неготоже есть апельсин в холодильнике, но с его точки зрения никакогоотношения к его гипотезе апельсин не имеет . . .Другой парадокс: с точки зрения формальной логики утверждения «кто не с нами, тот против нас» и «кто не против нас, тот снами» равносильны.Последнее (и очевидное) правило p ↔ ¬¬p называется снятиемдвойного отрицания. 2. Перечисленные эквивалентности соответствуют свойствам операцийна множествах: например, первая гарантирует, что P ∩ Q = Q ∩ P длялюбых множеств P и Q.
Какие утверждения соответствуют остальнымэквивалентностям?3. Две формулы, содержащие только переменные и связки ∧, ∨ и ¬,эквивалентны. Докажите, что они останутся эквивалентными, если всюдузаменить ∧ на ∨ и наоборот.Далеко не все тавтологии имеют ясный интуитивный смысл. Например, формула (p → q) ∨ (q → p) является тавтологией (если одноиз утверждений p и q ложно, то из него следует всё, что угодно; еслиоба истинны, то тем более формула истинна), хотя и отчасти противоречит нашей интуиции — почему, собственно, из двух никак несвязанных утверждений одно влечёт другое? Ещё более загадочна14Логика высказываний[гл. 1]тавтология((p → q) → p) → p(хотя её ничего не стоит проверить с помощью таблиц истинности).Отступление о пользе скобок. На самом деле наше определениеистинности содержит серьёзный пробел.
Чтобы обнаружить его, зададим себе вопрос: зачем нужны скобки в формулах? Представимсебе, что мы изменим определение формулы, и будем говорить, чтоP ∧ Q и P ∨ Q являются формулами для любых P и Q. Останутсяли наши рассуждения в силе?Легко понять, что мы столкнёмся с трудностью при определении булевой функции, соответствующей формуле. В этом определении мы подставляли нули и единицы на место переменных и затемвычисляли значение формулы с помощью таблиц истинности длясвязок. Но теперь, когда мы изменили определение формулы, формула p ∧ q ∨ r может быть получена двумя способами — из формулp ∧ q и r с помощью операции ∨ и из формул p и q ∨ r с помощью операции ∧. Эти два толкования дадут разный результат при попыткевычислить значение 0 ∧ 0 ∨ 1.Из сказанного ясно, что скобки нужны, чтобы гарантировать однозначность синтаксического разбора формулы. Точнее говоря, верно такое утверждение:Теорема 2 (однозначность разбора).
Пропозициональная формула, не являющаяся переменной, может быть представлена ровно водном из четырёх видов (A ∧ B), (A ∨ B), (A → B) или ¬A, где Aи B — некоторые формулы, причём A и B (в первых трёх случаях)восстанавливаются однозначно. Формальное доказательство можно провести так: назовём скобочным итогом разницу между числом открывающихся и закрывающихся скобок. Индукцией по построению формулы легко доказатьтакую лемму:Лемма. Скобочный итог формулы равен нулю. Скобочный итоглюбого начала формулы неотрицателен и равен нулю, лишь еслиэто начало совпадает со всей формулой, пусто или состоит из однихсимволов отрицания.Слова «индукцией по построению» означают, что мы проверяемутверждение для переменных, а также доказываем, что если оноверно для формул A и B, то оно верно и для формул (A∧B), (A∨B),(A → B) и ¬A.[п.
2]Полные системы связок15После того как лемма доказана, разбор формулы проводится так:если она начинается с отрицания, то может быть образована лишьпо третьему правилу. Если же она начинается со скобки, то надоскобку удалить, а потом искать непустое начало, имеющее нулевойскобочный итог и не оканчивающееся на знак логической операции.Такое начало единственно (как легко проверить, используя лемму).Это начало и будет первой частью формулы. Тем самым формуларазбирается однозначно. Нет смысла вдаваться в подробности этого (несложного) рассуждения: вообще-то алгоритмы разбора формул — это отдельная большая и практически важная тема (в первую очередь в связи с компиляторами).
Приведённый нами алгоритм далеко не оптимален. Сдругой стороны, мы вообще можем обойти эту проблему, потребовав,чтобы при записи формул левая и правая скобки, окружающие формулу, связывались линией — тогда однозначность разбора формулыне вызывает вопросов, и больше ничего нам не надо.В дальнейшем мы будем опускать скобки, если они либо не играют роли (например, можно написать конъюнкцию трёх членов, неуказывая порядок действий в силу ассоциативности), либо ясны изконтекста.4. Польский логик Лукасевич предлагал обходиться без скобок, записывая в формулах сначала знак операции, а потом операнды (без пробелови разделителей). Например, (a + b) × (c + (d × e)) в его обозначениях запишется как ×+ab+c×de. Эту запись ещё называют польской записью.Обратная польская запись отличается от неё тем, что знак операции идётпосле операндов.
Покажите, что в обоих случаях порядок действий восстанавливается однозначно.1.2. Полные системы связокРассматриваемая нами система пропозициональных связок (в неёвходят ∧, ∨, →, ¬) полна в следующем смысле:Теорема 3 (Полнота системы связок). Любая булева функция (слюбым числом аргументов) может быть записана в виде пропозициональной формулы.
Проще всего пояснить это на примере. Пусть, например, булевафункция ϕ(p, q, r) задана таблицей 1.4.В таблице есть три строки с единицами в правой колонке — трислучая, когда булева функция истинна (равна 1). Напишем три конъюнкции, каждая из которых покрывает один случай (а в остальных16Логика высказыванийp00001111q00110011r ϕ(p, q, r)0110001100100011[гл. 1](¬p ∧ ¬q ∧ ¬r)∨∨(¬p ∧ q ∧ r)∨∨(p ∧ q ∧ r)Таблица 1.4. Булева функция и задающая её формула.строках ложна), и соединим их дизъюнкцией. Нужная формула построена.Ясно, что аналогичная конструкция применима для любой таблицы (с любым числом переменных).
Для формул подобного вида есть специальное название: формулы в дизъюнктивной нормальной форме. Более подробно: литералом называется переменная или отрицание переменной, конъюнктом называется произвольная конъюнкция литералов, а дизъюнктивной нормальной формой называется дизъюнкция конъюнктов. Внашем случае в каждый конъюнкт входит n литералов (где n — число переменных), а число конъюнктов равно числу строк с единицамии может меняться от нуля (тогда, правда, получается не совсем формула, а «пустая дизъюнкция», и её можно заменить какой-нибудьвсегда ложной формулой типа p ∧ ¬p) до 2n (если булева функциявсегда истинна).5. Длина построенной в доказательстве теоремы 3 формулы зависитот числа единиц: формула будет короткой, если единиц в таблице мало.А как написать (сравнительно) короткую формулу, если в таблице малонулей, а в основном единицы?Иногда полезна двойственная конъюнктивная нормальная форма, которая представляет собой конъюнкцию дизъюнктов.
Каждыйдизъюнкт состоит из литералов, соединённых дизъюнкциями. Теорему 3 можно теперь усилить так:Теорема 4. Всякая булева функция может быть выражена формулой, находящейся в дизъюнктивной нормальной форме, а такжеформулой, находящейся в конъюнктивной нормальной форме. Первая часть утверждения уже доказана. Вторая часть ана-[п. 2]Полные системы связок17логична первой, надо только для каждой строки с нулём написатьподходящий дизъюнкт.Можно также представить функцию ¬ϕ в дизъюнктивной нормальной форме, а затем воспользоваться законами Де Моргана, чтобы внести отрицание внутрь.
6. Проведите второй вариант рассуждения подробно.Вообще говоря, определение нормальной формы не требует, чтобы в каждом конъюнкте (или дизъюнкте) встречались все переменные. (Повторять переменную больше одного раза смысла нет; если,например, переменная и её отрицание входят в одну конъюнкцию,то эта конъюнкция всегда ложна и её можно выбросить.)7. Приведите пример булевой функции n аргументов, у которой любаядизъюнктивная или конъюнктивная нормальная форма содержит лишьчлены длины n. (Указание: рассмотрите функцию, которая меняет своёзначение при изменении значения любой переменной.)Заметим, что при доказательстве теоремы 3 мы обошлись безимпликации. Это и не удивительно, так как она выражается черездизъюнкцию и отрицание:(p → q) ↔ (¬p ∨ q)(проверьте!).
Мы могли бы обойтись только конъюнкцией и отрицанием, так как(p ∨ q) ↔ ¬(¬p ∧ ¬q),или только дизъюнкцией и отрицанием, так как(p ∧ q) ↔ ¬(¬p ∨ ¬q)(обе эквивалентности вытекают из законов Де Моргана; их легкопроверить и непосредственно). Как говорят, система связок ∧, ¬, атакже система связок ∨, ¬ являются полными. (По определению этоозначает, что с их помощью можно записать любую булеву функцию.)8. Докажите, что система связок ¬, → полна.
(Указание: как записатьчерез них дизъюнкцию?)А вот без отрицания обойтись нельзя. Система связок ∧, ∨, →неполна — и по очень простой причине: если все переменные истинны, то любая их комбинация, содержащая только указанные связки,истинна. (Как говорят, все эти связки «сохраняют единицу».)9. Любая формула, составленная только с помощью связок ∧ и ∨, задаёт монотонную булеву функцию (в том смысле, что от увеличения значения любого из аргументов значение функции может только возрасти —18Логика высказываний[гл. 1]или остаться прежним).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
