![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Нетрудно убедиться, что имеют место следующие равносильности:
законы де Моргана для кванторов
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; Прочитано: 927 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!