Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Нетрудно убедиться, что имеют место следующие равносильности:
законы де Моргана для кванторов
1) ;
2) .
выражение кванторов одного через другой
3) ;
4) ;
законы пронесения кванторов через конъюнкцию и дизъюнкцию
5) ;
6) ;
7) ;
8) ;
законы перенесения кванторов через импликацию
9) ;
10) ;
11) ;
12) ;
законы коммутативности для кванторов
13) ;
14) ;
тождественно истинные импликации
15) ;
16) ;
17) .
Докажем некоторые из этих тождеств.
1) Пусть ‑ предикат, заданный на множестве М. Для доказательства истинности тождества нужно убедиться, что обе части эквивалентности одновременно истинны или одновременно ложны. В самом деле, высказывание истинно тогда и только тогда, когда высказывание ложно, что возможно тогда и только тогда, когда предикат опровержим. Далее, опровержимость предиката означает выполнимость его отрицания , что равносильно истинности высказывания . Итак, высказывание истинно тогда и только тогда, когда истинно высказывание , что и доказывает тождество.
Тождество 2) предлагается проверить самостоятельно.
Тождества 3) и 4) вытекают непосредственно из тождеств 1) и 2) и закона двойного отрицания.
5) Пусть предикаты и определенны на некотором множестве М. Докажем его истинность . Высказывание истинно тогда и только тогда, когда предикат тождественно истинен, что на возможно тогда и только тогда, когда оба предиката и тождественно истинны. Далее, тождественная истинность предикатов и равносильна истинности высказываний и соответственно, что равносильно истинности их конъюнкции . Итак, левая и правая части тождества одновременно истинны и одновременно ложны, что доказывает его истинность.
Тождества 6) и 7) предлагается доказать в качестве упражнения.
8) В этом тождестве — нульместный предикат (конкретное высказывание), а ‑ предикат, заданный на множестве М. Докажем его истинность . Действительно, высказывание истинно тогда и только тогда, когда предикат выполним. Последнее возможно, если и только если предикаты и выполнимы. (Напомним, что под выполнимостью нульместного предиката (высказывания) понимается его истинность.) Далее, выполнимость предиката и истинность высказывания равносильны истинности высказываний и , а значит, и истинности их конъюнкции . Это и доказывает тождество.
9) Пусть ‑ предикат, заданный на множестве М. Отметим, что предикат в тождествах 9), 10), 11), и 12) может быть не только нульместным, но и любым п -местным, важно лишь, чтобы в него не входила предметная переменная х. То есть имеет вид и определен на множестве . Для краткости будем считать, что ‑ одноместный предикат .
Предположим, что данное тождество не является истинным. В этом случае предикат (от у) ‑ опровержим, т.е. обращается в ложное высказывание при подстановке вместо предметной переменной у некоторого конкретного предмета :
.
Эквивалентность ложна, если ее члены принимают разные значения истинности, т.е. здесь могут представиться две возможности:
первая
; (1)
(2)
и вторая
; (3)
(4)
Рассмотрим первую возможность. Из формулы (2), по определению импликации, имеем
; (5)
. (6)
Далее, из формулы (5) и по определению квантора существования заключаем, что предикат выполним, т.е. для некоторого
. (7)
Вернемся к соотношению (1). По определению квантора общности предикат тождественно истинен. В частности, если вместо предметной переменной х подставить , то получим истинное высказывание . Но, учитывая (6) и (7), получаем . Противоречие.
Рассмотрим вторую возможность, выраженную в соотношениях (3), (4). Из формулы (3), на основании определения квантора общности, следует, что предикат опровержим, т.е. для некоторого . Тогда по определению импликации получим
, . (8)
Учитывая второе из соотношений (8), из соотношения (4) заключаем, что . Последнее означает тождественную ложность предиката . В частности, для предмета имеем , что противоречит первому из соотношений (8).
Итак, в каждом случае приходим к противоречию, доказывающему невозможность сделанного предположения. Следовательно, данное тождество истинно.
Тождества 10), 11) доказать самостоятельно.
12) Пусть ‑ предикат, заданный на множестве М, а ‑ на множестве . Предположим, что данное тождество не является истинным. Тогда предикат (от у) опровержим, опровержим, т.е. обращается в ложное высказывание при подстановке вместо предметной переменной у некоторого конкретного предмета :
,
Эквивалентность ложна в двух случаях. Во-первых, когда
; (1)
, (2)
и, во-вторых, когда
; (3)
. (4)
Рассмотрим первый случай. Из соотношения (2), по определению импликации, заключаем:
; (5)
. (6)
Соотношение (6) свидетельствует о том, что предикат тождественно ложен. Далее, соотношение (1) показывает, что предикат выполним. Учитывая соотношение (5), получаем: существует такой элемент , что . Последнее противоречит доказанной выше тождественной ложности предиката . Получить противоречие во втором случае, выраженном в соотношениях (3), (4), предлагается самостоятельно. Таким образом, рассматриваемое тождество справедливо.
Тождества 13), 14) и импликации 15), 16 докажите самостоятельно.
17) Пусть предикат , определенный на множестве , Предположим, что импликация ложна, тогда
; (1)
. (2)
Из соотношения (1) по определению квантора существования следует, что предикат (от у) выполним, т.е. для некоторого . Последнее, по определению квантора общности, означает, что предикат тождественно истинен на . Следовательно, тождественно истинным на будет и одноместный (от х) предикат . Но тогда, по определению квантора общности, , что противоречит соотношению (2). Следовательно, данная импликация тождественно истинна.
Дата публикования: 2015-03-26; Прочитано: 882 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!