2Дискретка / РГЗ / РГЗ 3..ИВ ИП
.pdf
Ч а с т ь 3 . ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ И ПРЕДИКАТОВ
Срок сдачи задания:
на последнем практическом занятии по теме «Исчисление предикатов».
Время защиты: по указанию преподавателя.
Содержание задания:
Задача 1. Доказать общезначимость формулы.
Задача 2. Записать в заданной модели формулы, выражающие заданные утверждения. Для полученной формулы построить приведенную нормальную формулу (ПНФ) с минимальным количеством переменных.
Примечание: в каждом варианте даны два утверждения. Задача 3. Построить вывод в исчислении высказываний.
Требования к оформлению:
Задача 1. Пример решения типового варианта задания с необходимыми пояснениями (см. также примере 37 (с.97) учебного пособия).
Доказать общезначимость формулы $x"yP(x, y) É "y$xP(x, y) .
Докажем от противного. Пусть наша формула не является общезначимой,
тогда
1 |
$x"yP(x, y) É "y$xP( x, y) = Л |
|
2 |
Импликация равна Л, только если |
|
3 |
x yP(x, y) = И |
y xP(x, y) = Л , |
|
(частное суждение) |
(частное суждение) |
4 |
Найдется константа а из области |
|
|
определения переменной x , такая |
¾//¾ |
|
что |
|
|
yP(а, y) = И |
|
|
(общее суждение) |
|
5 |
|
Найдется константа b из области оп- |
|
¾//¾ |
ределения переменной y , такая что |
|
¬ xP(x,b) = И |
|
|
|
|
|
|
(общее суждение) |
6 |
Для всех y , а значит, и для y = b |
¾//¾ |
|
верно |
|
|
P(а,b) = И |
|
7 |
|
Для всех x , а значит, и для x = a |
|
¾//¾ |
верно |
|
|
¬P(а,b) = И , т.е. P(а,b) = Л |
|
противоречие |
|
Задача 2. Ниже приведен пример решения типового варианта задания с необходимыми пояснениями.
Записать в модели M = L; E( |
) ,P( |
),C( |
), M ( ),W ( ) |
формулы, |
выражаю- |
|||
2 |
|
2 |
2 |
1 |
1 |
|
|
|
1 |
|
|
|
|
|
|
|
|
щие следующие утверждения: |
|
2) x и y – двоюродные братья, |
|
|||||
1) У каждого есть отец и мать; |
|
|
||||||
если L – множество людей; E (x, y) "x и y |
− один и тот же человек"; |
|
||||||
P(x, y) "x родитель y"; |
|
C (x, y) |
" x и y |
− супруги"; |
|
|
||
M (x) " x − мужчина"; |
W (x) "x − женщина". |
|
|
|||||
1) Предикат, формализующий выражение «У каждого есть |
y |
z |
||||||
отец и мать» является 0-местным предикатом, т.е. высказыванием. |
|
|
||||||
Изобразим схематично данное высказывание, введя следующие |
|
x |
||||||
переменные: y – отец x , z – мать x . Окончательно, получим: |
|
|||||||
B = «У каждого есть отец и мать» = x( y(P(y, x) M ( y)) z (P(z, x) W (z))).
Построим теперь приведенную нормальную формулу, используя эквива- лентные соотношения логики предикатов (учебное пособие с.99):
|
6 г |
|
|
B = x( y(P(y, x) M ( y)) z (P(z, x) W (z)))= |
|
||
= x y((P( y, x) M( y)) z(P(z, x) W(z))) |
6 г |
|
|
= . |
|
||
= x y z ((P(y,x) M ( y)) (P(z, x) W (z))) |
q |
||
2) Предикат, формализующий выражение « x и y |
– двою- |
||
|
|||
родные братья» является 2-местным предикатом. Пусть |
z |
p |
|
Br(x, y) =« x и y – двоюродные братья». |
|||
Изобразим схематично данное высказывание, введя следую- |
|
||
щие переменные: q – общий родитель z и p , z – родитель x , p – x |
y |
||
родитель y . Окончательно, получим:
Br(x, y) = M (x) M ( y) q z p(¬E(z, p) P(q, z) P(q, p)P(z, x) P( p, y)).
Приведенная нормальная формула для данного предиката, с учетом свой- ства 6г, имеет вид:
Br(x, y) = q z p(M (x) M (y) ¬E(z, p) P(q, z) P(q, p)P(z, x) P( p, y))
Задача 3.
1.Если при построении вывода использовалась теорема о дедукции, то построение основного вывода необходимо оформлять в таблице, аналогично, примеру, приведенному в учебном пособии (с.87).
2.Если для построения вывода использовалась подсказка, то все форму- лы, присутствовавшие в ней, должны быть выделены в работе.