Закон де моргана для операции или и операции и

Законы де Моргана для кванторов

а)

;

б)

.

Доказательство. Докажем тождественную истинность формулы а). (Тождественную истинность формулы б) предлагается проверить самостоятельно.) Данная формула замкнута, т. е. не имеет свободных предметных переменных. Поэтому, подставив в эту формулу вместо предикатной переменной любой конкретный одноместный предикат , определенный на некотором множестве , получим высказывание

Для доказательства его истинности нужно убедиться, что обе части эквивалентности одновременно истинны или одновременно ложны. В самом деле, высказывание истинно тогда и только тогда, когда высказывание ложно, что возможно на основании определения 20.1 тогда и только тогда, когда предикат опровержим.

https://www.youtube.com/watch?v=ytcreatorsru

Далее, опровержимость предиката означает выполнимость его отрицания (обдумайте это!), что равносильно на основании определения 20.3 истинности высказывания . Итак, высказывание истинно тогда и только тогда, когда истинно высказывание . Следовательно, высказывание (1) истинно, что и доказывает тождественную истинность формулы а).

Непосредственно из этой теоремы и закона двойного отрицания (теорема 3.1, в) вытекает следствие.

Доказательство. Тождественная истинность первых двух формул достаточно очевидна (проверьте самостоятельно).

Предположим, что формула в) — не тавтология. Тогда существует такой предикат , определенный на множествах и , что высказывание

ложно. Импликация ложна, если и только если

Из соотношения (1) по определению квантора существования следует, что предикат (от ) выполним, т.е. для некоторого . Последнее, по определению 20.1 квантора общности, означает, что предикат тождественно истинен на . Следовательно, тождественно истинным на будет и одноместный (от ) предикат . Но тогда, по определению квантора общности, , что противоречит соотношению (2). Следовательно, данная формула — тавтология. Теорема доказана.

Во всех доказанных тавтологиях предикатные переменные нульместны, одноместны или (в последней теореме) двухместны. Сохранится ли тождественная истинность этих формул, если считать, что входящие в них предикатные переменные зависят от произвольного числа предметных переменных? Положительный ответ содержится в следующей теореме.

Теорема 21.15.Если в тавтологиях теорем 21.9–21.14 считать, что предикатные переменные зависят от произвольного конечного числа предметных переменных, то полученные формулы будут также тавтологиями логики предикатов.

Доказательство. При доказательстве теоремы 21.12 уже была предпринята попытка к расширению смысла приведенных там тавтологий: под предикатной переменной понималась n-местная предикатная переменная . Можно было бы и под одноместной предикатной переменной понимать m-местную предикатную переменную , а квантор общности рассматривать по считая, что не входит в число предметных переменных предикатной переменной .

Докажем, например, тождественную истинность формулы из теоремы 21.11, в, считая m-местной предикатной переменной , a — n-местной предикатной переменной . Причем пусть не содержится среди предметных переменных , хотя некоторые (или все) из переменных могут содержаться среди переменных . Итак, требуется доказать тождественную истинность формулы

ПОДРОБНЕЕ:  Закон О Физической Культуре и Спорте в РФ N 329-ФЗ

Подставим вместо предикатных переменных и конкретные предикаты и , определенные на множествах и соответственно. Получим (m-1 n)-местный предикат

определенный на множествах и (в случае, если некоторые переменные встречаются среди переменных «местность» полученного предиката будет меньше). Докажем тождественную истинность данного предиката. Для этого проверим, что он превратится в истинное высказывание для произвольных элементов и множеств и соответственно.

Действительно, рассмотрим одноместный (от ) предикат , определенный на множестве и полученный из предиката в результате подстановки вместо предметных переменных элементов соответственно, и высказывание . Подставим их в тавтологию теоремы 21.11, в вместо одноместной предикатной переменной и нульместной предикатной переменной соответственно. Получим истинное высказывание

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

Замечание 21.16. В распространении взгляда на тавтологии, выраженного в теоремах 21.9–21.14, можно пойти еще дальше: считать, что буквы и представляют собой произвольные формулы логики предикатов, а не просто n-местные предикатные переменные (представляющие собой на основании определения 21.1 так называемые элементарные или атомарные формулы). Получаемые формулы также будут тавтологиями логики предикатов.

Закон де моргана для операции или и операции и

Рекомендуется самостоятельно проделать пропущенные доказательства тождественной истинности формул логики предикатов в теоремах данной лекции. Такая работа позволит глубже проникнуть в сущность понятий «для всех» и «существует», научит различать их и выделять в математической практике. Эти знания и навыки будут способствовать более отчетливому осознанию будущими учителями математики природы математических понятий, строения доказательств математических теорем, образованию значительного пласта логической и общематематической культуры.

Выражение кванторов одного через другой

а)

;

б)

.

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

Пронесение кванторов через конъюнкцию и дизъюнкцию

Доказательство. а) Подставим вместо предикатных переменных и конкретные предикаты и , определенные на некотором множестве . Формула превратится в высказывание

Докажем его истинность. На основании определения 20.1 высказывание истинно тогда и только тогда, когда предикат тождественно истинен, что на основании следствия 19.7 возможно в том и только в том случае, когда оба предиката и тождественно истинны. Далее, тождественная истинность предикатов и равносильна, ввиду определения 20.

ПОДРОБНЕЕ:  Аренда земельных участков - Земельное право

Тождественную истинность формул б) и в) предлагается доказать в качестве упражнения.

А

г) В этой формуле — нульместная предикатная переменная. Поэтому подставим в данную формулу вместо конкретный одноместный предикат , определенный на некотором множестве , а вместо — конкретное высказывание . Формула превратится в высказывание

Докажем его истинность. Действительно, на основании определения 20.3 высказывание истинно тогда и только тогда, когда предикат выполним. Последнее возможно, если и только если предикаты и выполнимы. (Напомним, что в конце предыдущего параграфа было условлено под выполнимостью нульместного предиката (высказывания) понимать его истинность.

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

Для формулы (3) такими предикатами могут служить, например, следующие предикаты, заданные над множеством всех вещественных чисел «» и «». Они посылку обратной импликации превращают в истинное высказывание , а заключение — в ложное высказывание .

Для формулы (4) подойдут предикаты, также заданные над «» и «», превращающие посылку обратной импликации в истинное высказывание , а следствие — в ложное высказывание .

Отметим, что тем не менее равносильное пронесение квантора общности через дизъюнкцию и квантора существования через конъюнкцию возможно. Это тот случай, когда один из членов дизъюнкции или конъюнкции не зависит от той предметной переменной, квантор по которой проносится (см. теорему 21.11, пункты в, г).

М

а) предположим, что данная формула не является тавтологией. В этом случае существуют такие конкретные предикаты и , определенные на множествах и соответственно, что предикат (от )

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

первая

и вторая

Рассмотрим первую возможность. Из формулы (2), по определению 1.7 импликации, имеем

Далее, из формулы (5) и по определению 20.3 квантора существования заключаем, что предикат выполним, т.е.

Рассмотрим вторую возможность, выраженную в соотношениях (3), (4). Из формулы (3), на основании определения 20.1 квантора общности, следует, что предикат опровержим, т.е. для некоторого . Тогда по определению 1.7 импликации получим

Учитывая второе из соотношений (8), из соотношения (4) заключаем, что . Последнее означает тождественную ложность предиката (см. определение 20.3). В частности, для предмета имеем , что противоречит первому из соотношений (8).

Итак, в каждом случае приходим к противоречию, доказывающему невозможность сделанного предположения. Следовательно, данная формула — тавтология.

г) Предположим, что данная формула не является тавтологией. Тогда существуют такие конкретные предикаты и , определенные на множествах и соответственно, что предикат (от )

ПОДРОБНЕЕ:  Материнский капитал изменения в законе на 2018 год || Материнский капитал изменения в законе на 2018 год

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

Эквивалентность ложна в двух случаях. Во-первых, когда

и, во-вторых, когда

Соотношение (6) свидетельствует о том, что предикат тождественно ложен (определение 20.3). Далее, соотношение (1) показывает, на основании того же определения 20.3, что предикат выполним. Учитывая соотношение (5), получаем: существует такой элемент , что . Последнее противоречит доказанной выше тождественной ложности предиката .

Получить противоречие во втором случае, выраженном в соотношениях (3), (4), предлагается самостоятельно. Таким образом, рассматриваемая формула — тавтология.

Докажите тождественную истинность двух оставшихся формул.

Проанализируем теперь ситуацию, связанную с пронесением кванторов через импликацию, а также с их вынесением за знак импликации. В случаях, когда один из членов импликации (посылка или заключение) не зависит от той предметной переменной, по которой проносится квантор, равносильность также возможна. Но ситуация здесь несколько отличается от той, которая имеет место в случаях конъюнкции и дизъюнкции.

Если от предметной переменной, стоящей под знаком квантора, не зависит посылка импликации, то соответствующий квантор без изменения проносится к заключению импликации (теорема 21.12, пункт в). Если же от предметной переменной, стоящей под знаком квантора, не зависит заключение импликации, то соответствующий квантор при пронесении его к посылке импликации переворачивается, т. е.

Докажите это самостоятельно. То, что обратная импликация не будет тавтологией, подтверждает пример двух предикатов » делится на 4″ и «x четно», заданных над множеством натуральных чисел.

Проверьте, что формулы действительно являются тавтологиями, а обратные импликации таковыми не являются.

В то же время аналогичная конструкция с квантором существования

уже не будет тавтологией. Пример: » — четно», «», . Не будет тавтологией и обратная импликация. Пример: «» и «», .

Удаление квантора общности и введение квантора существования

а)

;

б)

.

Доказательство. Проверим, что формула а) тождественно истинна (соответствующую проверку для формулы б) выполнить самостоятельно). Предположим, что формула а) не тождественно истинна. Это значит: существует такой предикат , определенный на некотором множестве , что предикат (от ) опровержим, т.е. превращается в ложное высказывание при подстановке вместо у некоторого . Последнее означает, что

https://www.youtube.com/watch?v=ytdevru

Из соотношения (1) заключаем, что предикат тождественно истинный. Но это противоречит соотношению (2). Следовательно, сделанное предположение неверно, и данная формула — тавтология.

Понравилась статья? Поделиться с друзьями:
Adblock
detector