Учебное пособие Владивосток Издательский дом Дальневосточного федерального университета 2013 ббк 22. 12 К 93

Пусть предикат определен на множестве M = N N и означает «x<y».

1. 
   Какие из следующих предикатов тождественно истинные и какие тождественно ложные:
   
   1. 
      - выполнимый предикат Q₁(y)
      
   2. 
      – тождественно-ложный предикат Q₂(y)
      
   3. 
      – тождественно-истинный предикат Q₃(y)
      
   4. 
      – тождественно-ложный предикат Q₄(y)
      
2. 
   Для тех предикатов из 1), которые не являются ни тождественно истинными, ни тождестывенно ложными, указать область истинности и область ложности.
   
   1. 
      Q₁ = {2,3,…,N}
      

15. 
    Доказать следующую равносильность:
    

Доказательство:
Так как – предикатная переменная, подставим вместо нее конкретный предикат и докажем, что:

По определению:

1. 
   Пусть , тогда предикат A(x) – тождественно-истинный, отсюда – тождественно-ложный предикат, отсюда по определению связывания квантором существования по переменной x предиката B(x) получаем выказывание
   

Отсюда следует, что высказывание , значит отрицание этого высказывания является истинным:

2. 
   Пусть (*)
   

По определению:

Из (*) следует, что – опровержимый предикат, тогда его отрицание - выполнимый предикат.
Тогда высказывание (**)
А отрицание высказывания (**) равно нулю: