Здавалка
Главная | Обратная связь

Задания для самостоятельного выполнения

⇐ ПредыдущаяСтр 9 из 11Следующая ⇒

1.Пусть предикат P(x, y) определен на множествах: X={a1,a2 a3,a4}, Y={b1,b2,b3,b4,b5,b6,b7,b8} и имеет таблицу истинности. С помощью кванторов постройте высказывания и определите их истинность:

0)

X Y
b1 b2 b3 b4 b5 b6 b7 b8
a1 Л И Л И Л И И Л
a2 Л И И И Л И И Л
a3 И И Л И Л Л Л Л
a4 И И Л И Л Л Л Л

1)

X Y
b1 b2 b3 b4 b5 b6 b7 b8
a1 И Л Л И Л И И Л
a2 Л Л Л Л Л Л Л Л
a3 И И Л И Л Л Л Л
a4 Л Л Л И И Л И Л

2)

X Y
b1 b2 b3 b4 b5 b6 b7 b8
a1 И Л И Л И Л И Л
a2 Л И И Л Л Л Л И
a3 И Л Л Л Л Л Л И
a4 Л И Л И И Л Л И

3)

X Y
b1 b2 b3 b4 b5 b6 b7 b8
a1 И И Л И И Л Л И
a2 Л Л И Л И И И И
a3 И Л И Л И И Л И
a4 И И Л И Л Л Л И

4)

X Y
b1 b2 b3 b4 b5 b6 b7 b8
a1 Л И Л И Л И И Л
a2 Л И И И Л И И Л
a3 Л И Л И Л Л Л Л
a4 И Л И Л Л Л Л Л

5)

X Y
b1 b2 b3 b4 b5 b6 b7 b8
a1 И И Л И И Л Л Л
a2 Л И И И И Л Л И
a3 И И Л Л И И Л И
a4 И Л И Л И Л Л Л

6)

X Y
b1 b2 b3 b4 b5 b6 b7 b8
a1 Л И Л И И И И Л
a2 Л И И И И И И Л
a3 Л Л И И И Л Л Л
a4 И Л Л И И И Л Л

7)

X Y
b1 b2 b3 b4 b5 b6 b7 b8
a1 И Л Л И Л И И Л
a2 И И Л Л Л И И Л
a3 И И Л И И И И Л
a4 И И Л Л И Л Л Л

8)

X Y
b1 b2 b3 b4 b5 b6 b7 b8
a1 И И Л И Л И Л И
a2 И Л Л И И Л И Л
a3 Л И Л И И Л Л И
a4 Л Л И И И Л Л Л

9)

X Y
b1 b2 b3 b4 b5 b6 b7 b8
a1 Л Л Л Л Л Л Л Л
a2 И И И И Л И И Л
a3 Л И Л И И И И И
a4 Л Л Л И И И Л И

Решение:

Y b1 b2 b3 b4 b5 b6 b7 b8
" x P(x, y)                
$x P(x, y)                
X " y P(x, y)   X $ y P(x, y)  
a1     a1    
a2     a2    
a3     a3    
a4     a4    
                           

2. Предикат R(x,y) определен на множествах: X={a1,a2,a3,a4,a5}, Y={b1,b2,b3,b4,b5,b6,b7,b8} и имеет таблицу истинности. С помощью кванторов постройте высказывания и определите их истинность:

0)

X Y
b1 b2 b3 b4 b5 b6 b7 b8
a1 Л Л Л Л Л И И И
a2 И И Л И И И Л Л
a3 И И Л И И Л Л Л
a4 Л Л Л И Л Л Л Л
a5 Л Л Л Л Л Л Л Л

1)

X Y
b1 b2 b3 b4 b5 b6 b7 b8
a1 Л И Л И Л И И Л
a2 Л Л Л И Л И Л Л
a3 И И И И Л И Л Л
a4 Л Л И И И И И И
a5 И Л Л И Л И Л Л

2)

X Y
b1 b2 b3 b4 b5 b6 b7 b8
a1 И Л И И И И И И
a2 И Л Л И Л Л Л И
a3 И Л Л И Л Л Л И
a4 И Л Л И И Л Л И
a5 И Л И И И И Л Л

3)

X Y
b1 b2 b3 b4 b5 b6 b7 b8
a1 И И Л И И Л Л И
a2 Л Л И Л И И И И
a3 И Л И Л И И Л И
a4 И И Л И Л Л Л И
a5 И Л И Л Л Л И Л

4)

X Y
b1 b2 b3 b4 b5 b6 b7 b8
a1 И И Л Л Л Л И Л
a2 И И И И Л И И Л
a3 И И И И Л Л Л Л
a4 И Л И Л Л Л Л Л
a5 Л Л Л Л Л Л И И

5)

X Y
b1 b2 b3 b4 b5 b6 b7 b8
a1 Л Л Л И И Л Л Л
a2 Л И И Л И Л Л И
a3 Л И Л Л И И Л Л
a4 И Л И Л И Л Л Л
a5 Л И Л И Л Л И Л

6)

X Y
b1 b2 b3 b4 b5 b6 b7 b8
a1 Л И Л И И И И И
a2 Л И И И И И И Л
a3 Л И И И И Л Л Л
a4 И Л Л И И И И И
a5 И Л Л И Л Л Л Л

7)

X Y
b1 b2 b3 b4 b5 b6 b7 b8
a1 И Л Л И И И И Л
a2 И И Л Л Л И И Л
a3 И И Л И И И И Л
a4 И И Л Л И И Л Л
a5 И И И Л Л Л Л Л

8)

X Y
b1 b2 b3 b4 b5 b6 b7 b8
a1 И И Л И И И И И
a2 И Л И И И Л И Л
a3 Л И Л И И Л Л И
a4 Л И И И И И Л Л
a5 И Л Л Л Л Л Л Л

9)

X Y
b1 b2 b3 b4 b5 b6 b7 b8
a1 Л И Л И Л Л Л Л
a2 И И И И И И И И
a3 Л И Л И И И И И
a4 Л Л Л И И И Л И
a5 Л Л Л И Л Л Л Л

Решение:

X " y R(x, y)   X $ y R(x, y)
a1     a1  
a2     a2  
a3     a3  
a4     a4  
a5     a5  
         
Y b1 b2 b3 b4 b5 b6 b7 b8
" x R(x, y)                
$x R(x, y)                
                         

3. Предикат А(x,y) определен на множествах: X={a1,a2,a3,a4,a5,a6}, Y={b1,b2,b3,b4,b5,b6,b7} и задан таблично. С помощью кванторов постройте высказывания и определите их истинность:

0)

X Y
b1 b2 b3 b4 b5 b6 b7
a1 Л И Л И Л И Л
a2 Л И И И Л И И
a3 И И Л И Л И Л
a4 И И Л И Л И Л
a5 Л И Л Л И И Л
a6 И И Л Л Л Л И

1)

X Y
b1 b2 b3 b4 b5 b6 b7
a1 Л И Л И Л Л И
a2 Л И И И Л Л Л
a3 И И Л И Л И И
a4 И И Л И Л И Л
a5 Л И Л И И Л И
a6 Л Л Л Л Л Л Л

2)

X Y
b1 b2 b3 b4 b5 b6 b7
a1 Л И Л И Л Л И
a2 Л И И И Л Л Л
a3 Л Л Л И Л Л И
a4 Л Л И И И И И
a5 Л И И Л И И Л
a6 Л И Л Л Л Л И

3)

X Y
b1 b2 b3 b4 b5 b6 b7
a1 Л И Л И И Л И
a2 И И Л Л Л Л Л
a3 И И Л И Л Л И
a4 Л И Л Л И И И
a5 И И Л И И И Л
a6 Л И И И Л И И

4)

X Y
b1 b2 b3 b4 b5 b6 b7
a1 И И Л И Л И Л
a2 Л И Л И Л И Л
a3 Л И Л И Л Л Л
a4 Л Л Л Л Л И И
a5 И И Л И И И Л
a6 И Л И Л И И И

5)

X Y
b1 b2 b3 b4 b5 b6 b7
a1 И Л Л И Л И Л
a2 Л Л Л И И Л Л
a3 Л И Л И И Л Л
a4 Л Л Л Л И Л И
a5 Л И Л И И И И
a6 Л Л Л Л Л Л И

 

6)

X Y
b1 b2 b3 b4 b5 b6 b7
a1 Л И Л И Л Л И
a2 Л Л И Л Л Л Л
a3 Л И Л И И Л Л
a4 Л И И Л Л Л И
a5 Л Л Л И И Л И
a6 И И Л Л И И И

7)

X Y
b1 b2 b3 b4 b5 b6 b7
a1 И Л Л И Л И Л
a2 Л Л Л И И Л Л
a3 Л И Л И И Л Л
a4 Л Л Л Л И Л И
a5 Л И Л И И И И
a6 Л Л Л Л Л Л И

8)

X Y
b1 b2 b3 b4 b5 b6 b7
a1 И Л Л Л И И И
a2 И Л Л Л Л И И
a3 И Л И И Л И И
a4 И Л И И Л И И
a5 Л И И И И И И
a6 Л И Л Л Л Л И

9)

X Y
b1 b2 b3 b4 b5 b6 b7
a1 Л Л Л И Л И И
a2 Л И Л Л И Л И
a3 Л И Л Л Л И Л
a4 И Л Л Л И Л Л
a5 И И Л Л И И И
a6 Л И Л Л Л Л И

Решение:

Y b1 b2 b3 b4 b5 b6 b7
" x A(x, y)              
$x A(x, y)              

 

 

X " y A(x, y)   X $ y A(x, y)  
a1     a1    
a2     a2    
a3     a3    
a4     a4    
a5     a5    
a6     a6    
           
  Высказывание Значение истинности
  "x "y A(x, y)  
  "x$ y A(x, y)  
  $ x"y A(x, y)  
  $ x$ y A(x, y)  
  "y$ x A(x, y)  
  $ y"x A(x, y)  
               

Виды форм логики предикатов

Две формулы логики предикатов А и В называются равносильными, если они равносильны на всякой области.

Пусть P(х), Q(х) и U(x,y) – переменные предикаты. Тогда имеют место равносильности:

Ø$x P(x) º "x ØP(x) Ø"x P(x) º $x ØP(x)
Ø("x P(x)Ú $y Q( y)) º $x ØP(x) & "y ØQ(y) Ø("x P(x) & $y Q(y)) º $x ØP(x) Ú "y ØQ(y)
Ø Ø "x P(x) º "x P(x) Ø Ø $x P(x) º $x P(x)
"x "y U(x, y) º "y "x U(x, y) $x $y U(x, y) º $y $x U(x, y) "x $y U(x, y) ¹ $y "x U(x, y) $x "y U(x, y) Þ "y $x U(x, y)
"x "x Q(x) º "x Q(x) $x $x Q(x) º $x Q(x) "x (P(x) & P(x)) º "x P(x) $x (P(x) Ú P(x)) º $x P(x)
"x P(x) & "y U(y) º "x"y (P(x) & U(y)) "x P(x) & "x U(x) º "x (P(x) & U(x))
$x P(x) Ú $y U(y) º $x$y (P(x) Ú U(y)) $x P(x) Ú $x U(x) º $x (P(x) Ú U(x))
$x P(x) & $x U(x) ¹ $x (P(x) & U(x)) $x P(x) & $x U(x) º $x $ a (P(x) & U(a))
"x P(x) Ú "x U(x) ¹ "x (P(x) Ú U(x)) "x P(x) Ú "x U(x) º "x "a (P(x) Ú U(a))
"x P(x) & $x U(x) º "x$a (P(x) & U(a)) "x P(x) Ú $x U(x) º "x$a (P(x) Ú U(a))

В логике предикатов различают два вида форм: приведенную и предваренную.

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

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

Алгоритм получения ПНФ:

1. выразите операции импликации и эквиваленции через конъюнкцию, дизъюнкцию и отрицание;

2. внесите символы отрицания так, чтобы они относились непосредственно к символам предикатов (и, таким образом, мы приводим исходную формулу к приведенной форме);

3. для формул, содержащих подформулы вида: "x P(x) Ú "x U(x), $xP(x) & $xU(x), "xP(x) & $xU(x), "xP(x) Ú $xU(x) введите новые связанные переменные;

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

⇐ Предыдущая234567891011Следующая ⇒






©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.