Выяснить существует ли формула f такая что формула g тождественно истинна

Равносильность, законы логики первого порядка

Общая схема изложения материала этого и двух следующих параграфов будет напоминать изложение материала в §3 – 5 главы 1.

Пример 1. Пусть P – символ двухместного предиката. Докажем, что формулы F(x) = (∀y)P(x, y) и G(x) = (∃y)P(x, y) равносильны. Возьмем интерпретацию ϕ с областью M. Пусть высказывание (ϕF)(a) истинно для a∈M. Истинность этого высказывания означает, что не для всякого y∈M высказывание (ϕP)(a, y) истинно. Следовательно, найдется b∈M, для которого высказывание (ϕP)(a, b) ложно. Если высказывание (ϕP)(a, b) ложно, то высказывание (ϕP)(a, b) истинно. Отсюда следует, что найдется y∈M такой, для которого высказывание (ϕP)(a, y) истинно. Это означает истинность высказывания (ϕG)(a). Мы доказали, что если высказывание (ϕF)(a) истинно, то высказывание (ϕG)(a) тоже истинно. Обратная импликация доказывается аналогично. Итак, значения истинности высказываний (ϕF)(a) и (ϕG)(a) при любом a∈M совпадают. Следовательно, формулы F(x) и G(x) равносильны.

Определение. Формула F(x₁, …, x_n) называется тождественно истинной, если для любой интерпретации ϕ с областью M высказывание (ϕF)(a₁, …, a_n) при любых a₁, …, a_n из M является истинным.

Пример 2. Рассмотрим формулу F(x) = (∀y)P(x, y)→P(x, c), где P – символ двухместного отношения, с – константа.

Докажем, что формула F(x) тождественно истинна. Возьмем интерпретацию ϕ с областью M и элемент а из M. Высказывание (ϕF)(a) равно (∀y)(ϕP)(a, y) → (ϕP)(a, ϕ(c)). Если посылка (∀y)(ϕP)(a, y) ложна, то вся импликация (ϕF)(a) истинна. Предположим, что посылка (∀y)(ϕP)(a, y) истинна. Это означает, что для всякого y∈M высказывание (ϕP)(a, y) истинно, в том числе оно истинно и для y = ϕ(c). Следовательно, истинны заключение (ϕP)(a, ϕ(c)) и вся импликация (ϕF)(a). Мы доказали, что высказывание (ϕF)(a) истинно для любого a∈M. Это означает, что формула F(x) является тождественно истинной.

Понятия равносильности и тождественной истинности в логике первого порядка связаны точно так же, как и в логике высказываний.

Теорема 2.1.Формулы F(x₁, …, x_n) и G(x₁, …, x_n) равносильны тогда и только тогда, когда формула

Доказательство теоремы 2.1 аналогично доказательству теоремы 1.1 и предлагается читателю в качестве упражнения.

Как и в случае логики высказываний, приведем список основных равносильностей – законов логики предикатов. Прежде всего, получим законы логики предикатов из законов 1 – 21 логики высказываний, понимая под F, G, H произвольные формулы логики предикатов. Дополним полученный список законами, специфичными для логики предикатов.

Оказывается, нет. Докажем это для случая, когда F(x) и G(x) – атомарные формулы. Пусть основное множество – множество натуральных чисел N, F(x) – предикат “x – четное число”, G(x) – предикат “x – нечетное число”. Обозначим эту интерпретацию буквой ϕ. Тогда ϕ[(∀x)(F(x)∨G(x))] = 1, но ϕ[(∀x)F(x) ∨ (∀x)G(x)] = 0. Аналогично, ϕ[(∃x)(F(x)&G(x))] = 0 и ϕ[(∃x)F(x) & (∃x)G(x)] = 1.

Рассмотрим законы 23 и 24. Они утверждают, что одноименные кванторы можно менять местами. Можно ли переставлять местами разноименные кванторы, сохраняя равносильность? Другими словами, равносильны ли формулы

Оказывается, тоже нет. В качестве основного множества опять возьмем множество натуральных чисел, F(x, y) будем считать атомарной формулой и поставим ей в соответствие предикат “x меньше y ”. Тогда левая формула будет истинной, правая – ложной.

Вернемся к законам 22 и 23. Мы отмечали, что квантор общности нельзя переносить через дизъюнкцию, а квантор существования – через конъюнкцию. Тем не менее, если одна из формул F или G не содержит переменной x (на которую навешивается квантор), то это делать можно. Запишем соответствующие законы:

Законы 22, 23, 28, 29 можно записать в общем виде:

где Q₁, Q₂ – кванторы ∀ или ∃, переменная u не входит в F(x), а переменная x не входит в G(u).

Для доказательства равносильности двух формул могут оказаться полезными следующие законы:

В законах 32 и 33 переменная z не входит в F(x), а переменная x не входит в F(z).

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

Пример 3. Проиллюстрируем его на примере следующей задачи: доказать равносильность формул:

Применив к формуле F последовательно законы 26, 27 и

20, получим, что формула F равносильна формуле

Далее, используя законы 18, 19 и 27 из F₁, получаем формулу

Осталось заметить, что в силу законов 17 и 20 в формуле F₂ подформулу (T(z) & P(x, z)) можно заменить на T(z) → P(x, z).

Подчеркнем, что доказательство равносильности двух формул обычно проводится с помощью законов логики первого порядка. Доказательство того, что формулы неравносильны осуществляется построением интерпретации, при которой одна формула истинна, другая ложна. Например так, как это было сделано выше для доказательства неравносильности формул (∀x)(F(x) ∨ G(x)) и (∀x)F(x) ∨

(∀x)G(x). Разумеется, формулы до построения интерпретации можно предварительно преобразовывать с помощью законов.

Логическое следствие

Пример 1. Пусть F₁ = (∀x)(P(x)→Q(x)&R(x)), F₂ = P(c), G = Q(c). Покажем, что формула G является логическим следствием формул F₁ и F₂. Возьмем интерпретацию ϕ с областью M такую, что высказывания ϕF₁ и ϕF₂ истинны. Элемент ϕ(c) обозначим буквой b. Истинность ϕF₂ означает, что высказывание (ϕP)(b) истинно. А истинность высказывания ϕF₁ означает, что для любого элемента x∈M истинно высказывание (ϕP)(x) → (ϕQ)(x)&(ϕR)(x). Поскольку это высказывание истинно для любого х, оно, в частности, истинно для x = b. Мы видим, что истинна импликация (ϕP)(b) → (ϕQ)(b)&(ϕR)(b) и ее посылка (ϕP)(b). Из таблицы истинности импликации следует истинность заключения (ϕQ)(b)&(ϕR)(b). Следовательно, истинно высказывание (ϕQ)(b). А это и есть ϕG. Мы доказали, что если истинны высказывания ϕF₁ и ϕF₂, то истинно высказывание ϕG, т.е. что G –логическое следствие F₁ и F₂.

Пример 2. В качестве второго примера докажем нелогичность рассуждения о первокурсниках, приведенное в §3. Мы записали это рассуждение в виде последовательности формул H₁, H₂, и H₃. Для доказательства нелогичности рассуждения надо найти интерпретацию ϕ, при которой формулы H₁ и H₂ истинны, а формула H₃ ложна. Пусть множество М состоит из трех элементов 2, 3, 4. Символы С, Л и П проинтерпретируем следующим образом:

т.е. П интерпретируется как тождественно ложный пре-

дикат. Символу З поставим в соответствие произвольный двухместный предикат. Тогда формулы H₁ и H₂ истинны, поскольку посылки импликаций этих формул ложны при любом x. А формула H₃ ложна. Чтобы убедиться в этом достаточно взять x = 2. Следовательно, рассуждение о первокурсниках нелогично.

Определение. Множество формул

& Q(x, y)), F₂ = (∀y)Q(c, y), F₃ = P(c)> выполнимо. Возьмем в качестве области интерпретации множество натуральных чисел N.Символы P, Q и с проинтерпретируем следующим образом:

Тогда высказывание ϕF₁ означает, что для любого натурального числа х найдется простое число y, которое не меньше х, высказывание ϕF₂ означает, что 1 –наименьшее натуральное число, а высказывание ϕF₃ означает, что 1 – непростое число. Ясно, что все эти высказывания истинны, и поэтому множество формул K выполнимо.

Понятия логического следствия и выполнимости в логике первого порядка связаны точно так же, как и в логике высказываний.

Доказательство теоремы 2.2 аналогично доказательству теоремы 1.2 и поэтому не приводится.

Нормальные формы

Как и в логике высказываний, в логике первого порядка вводятся нормальные формы. Мы рассмотрим две из них: предваренную нормальную и сколемовскую нормальную формы.

Определение. Формула G имеет предваренную нормальную форму (сокращенно: ПНФ), если

где Q₁, …, Q_n кванторы, а формула H не содержит кванторов.

Теорема 2.3.Для всякой формулы F существует формула G, равносильная F и имеющая предваренную нормальную форму.

Доказательство теоремы легко следует из анализа алгоритма приведения к ПНФ.

Источник

ИМКН Домашние задания по математической логике Тема: Высказывания и операции с ними»

Домашние задания по математической логике

Тема: «Высказывания и операции с ними»

I. Является ли формула F тождественно истинной (общезначимой)?

.

II. Существует ли формула F такая, что G является тождественно истинной?

.

III. Равносильны ли формулы F и G?

1.; .

2.;

3.; .

IV. Является ли формула G логическим следствием формул F1. Fk?

1.

2.

3.

4.

V. Записать следующие рассуждения в виде последовательности формул логики высказываний. Будет ли логичным рассуждение?

1. В бюджете возникнет дефицит, если не повысят пошлины. Если в бюджете возникнет дефицит, то расходы на социальные нужды сократятся. Следовательно, если повысят пошлины, то расходы на социальные нужды не сократятся.

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

Тема: «Нормальные формы логики высказываний»

1.

2.

VII. Привести к СДНФ.

1.

2.

VIII. Привести к КНФ.

1.

2.

Темы: «Метод резолюций» и «Контактные схемы»

IX. Доказать, что формула G является логическим следствием формул F1. Fk, используя метод резолюций:

1.

2.

3.

4.

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

2. Построить наименьшую контактную схему, открывающую дверь при нажатии кнопок директора и хотя бы одного из заместителей или всех кнопок заместителей директора (всего у директора три заместителя). Записать соответствующую формулу логики высказываний.

1. “Прямые x и y имеют общую точку”.

2. “Прямые x и y параллельны”.

3. “Прямые x, y и z образуют треугольник”.

XII. Выбрать подходящую сигнатуру и записать следующие рассуждения в виде последовательности формул логики предикатов.

Тема: «Равносильность формул логики предикатов»

XIII. Доказать неравносильность формул

1. и .

2. и .

XIV. Доказать равносильность формул

и .

Тема: «Нормальные формы логики предикатов»

XV. Привести формулу к ПНФ и СНФ.

.

Тема: «Логическое следствие логики предикатов»

XVI. Доказать нелогичность рассуждений.

Некоторые студенты нашей группы — болельщики «Спартака». А некоторые болельщики «Спартака» занимаются спортом. Следовательно, некоторые студенты нашей группы занимаются спортом.

Тема: «Метод резолюций логики предикатов»

XVII. Доказать логичность рассуждений.

Все студенты нашей группы — болельщики «Спартака», а некоторые занимаются спортом. Следовательно, некоторые из болельщиков «Спартака» занимаются спортом.

Тема: «Выполнимость в логике предикатов»

XVIII. Выполнимы ли формулы:

а) ;

б) ;

в) ?

XIX. Доказать тождественную истинность формулы

.

XX. Доказать, что следующая формула истинна во всякой конечной модели, но не тождественно истинна:

.

Источник

Раздел 1. Математическая логика

Тема 1. Логика высказываний

Логика предикатов в качестве составной и наиболее простой части содержит логику высказываний.

§1. Высказывания и операции над ними

§2. Формулы логики высказываний, интерпретация

§3. Равносильность и законы логики высказываний

§4. Логическое следствие.

§5. Нормальные формы в логике высказываний

§6. Контактные схемы.

Задачи

1. Определить, какая логическая связка используется в следующих выражениях: «А, если В», «коль скоро А, то В», «в случае А имеет место В», «как А, так и В», «для А необходимо В», «для А достаточно В», «А вместе с В», «А не имеет места», «A, только если B», «A, пока B», «или A, или B», «A одновременно с B», «A – то же самое, что и B».

2. Записать следующие рассуждения в виде последовательности формул логики высказываний.

2.1. Профсоюзы штата будут поддерживать губернатора, если он подпишет этот закон. Фермеры окажут ему поддержку, если он наложит на него вето. Очевидно, что он или не подпишет закон, или не наложит на него вето. Следовательно, губернатор потеряет голоса рабочих, объединенных в профсоюзы, или голоса фермеров.

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

2.3. Если завтра будет хорошая погода, то я буду кататься на коньках или я пойду на лыжах. Если я пойду на лыжах, то лучше поехать за город, а если буду кататься на коньках, то останусь в городе. Мне не хочется завтра в выходной день оставаться в городе. Следовательно, если завтра будет хорошая погода, то я пойду на лыжах.

3. Будут ли следующие формулы тождественно истинны:

4. Существует ли формула F такая, что формула G тождественно истинна:

5. Будут ли следующие формулы равносильны:

6. Доказать равносильность формул:

7. Доказать, что формула G является логическим следствием формул F₁,F₂. F_n:

8. Доказать, что формула G не является логическим следствием формул F₁,F₂. F_n:

10.1. Если Джонс не встречал этой ночью Смита, то Смит был убийцей или Джонс лжет. Если Смит не был убийцей, то Джонс не встречал Смита этой ночью, и убийство произошло после полуночи. Если убийство произошло после полуночи, то Смит был убийцей или Джонс лжет. Эксперты установили, что убийство произошло до полуночи. Следовательно, Смит был убийцей.

10.2. В бюджете возникнет дефицит, если не повысят пошлины. Если в бюджете возникнет дефицит, то расходы на социальные нужды сократятся. Следовательно, если повысят пошлины, то расходы на социальные нужды не сократятся.

10.3. Намеченная атака удастся, если захватить противника врасплох или его позиции плохо защищены. Захватить противника врасплох можно только, если он беспечен. Он не будет беспечен, если его позиции плохо защищены. Следовательно, намеченная атака не удастся.

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

11. Привести формулы к ДНФ:

12. Привести формулы к СДНФ:

13. Привести формулы к КНФ:

14. Для следующих схем построить эквивалентные им более простые цепи:

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

Ответы, указания и решения

Тема 2. Булевы функции

Тема 3. Логика предикатов

Тема 4. Метод резолюций

Раздел 2. Теория графов

Источник