Математическая логика и теория алгоритмов: Методические указания к практическим занятиям, страница 8

      Определение 12. Приведенной формой для формулы логики предикатов называется такая равносильная ей формула, в которой из операций алгебры высказываний имеются лишь операции     а  знаки отрицания  относятся лишь к предикатным переменным или к высказываниям. Предварённой нормальной формой для формулы логики предикатов называется такая её приведенная форма, в которой все кванторы стоят в её начале, а область действия каждого из них распространяется до конца формулы (либо  кванторы в формуле совсем отсутствуют).

Можно доказать  [3, c. 158-159], что для  каждой формулы логики предикатов существует предваренная нормальная  форма.

Упражнения

1.  Указать свободные и связанные переменные в следующих формулах:

                       

             

Ответы:   б)  связанная переменная,     свободная переменная;

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

2. Интерпретация замкнутой формулы состоит из следующих шагов [2, c.107]:

1) задается множество 

2) каждой предикатной букве, входящей в  местный предикатный символ, ставится в соответствие местный предикат, определенный на 

3) каждому нуль-местному  предикатному символу приписывается одно из значений истинности.

Если формула – открытая, то добавляется ещё один шаг:

4)каждому свободному вхождению переменной ставится в соответствие элемент множества 

      Пример. Дать интерпретацию открытой формуле 

1)  Пусть 

2)  предикатной букве    поставим в соответствие  предикат, заданный таблицей

1	0	1	0

а предикатной  букве  – предикат, заданный таблицей

1	2
1	0

3)   предикатному символу     припишем  значение  1  (истина);

4)  свободному вхождению переменной     припишем значение 1.

При такой интерпретации  данная формула  обращается в истинное высказывание. Действительно, существует      такое, что     истинно

 Следовательно, посылка (антецедент) импликации принимает значение 1, а заключение  (консеквент)     тоже истинно. Значит, импликация истинна.  

Дать интерпретации следующим формулам (см., например, [3, c. 144-145]:

3.  Для следующих формул найти равносильную им приведенную форму:

Ответы:  

     

     

4.  Привести следующие формулы к предваренной (пренексной) нормальной форме:

Ответы:  

Упражнения для самостоятельной работы

1.  Указать свободные и связанные переменные в следующих формулах:

Ответы:  и   связанные переменные,  свободная переменная.

и   связанные переменные, свободная переменная.

2.  Дать интерпретацию следующим формулам логики предикатов:

3.  Для следующих формул найти равносильную им приведенную форму:

 

Ответы:  Используя правило де Моргана для предикатов, имеем:

4.  Привести следующие формулы к предварённой (пренексной) нормальной форме:

Ответы: 

Занятие 6. Логика предикатов и алгебра множеств. Уравнения и

неравенства как логические функции (предикаты). Комплекс теорем в геометрии. Необходимые и достаточные условия

Тема «Уравнения и неравенства» лучше всего проясняется на основе понятия логической функции (предиката).

Рассмотрим вначале уравнения с одной переменной 

Определение 13. Уравнением

                                                   (1)

 называется  одноместный предикат с (предметной) переменной     имеющий вид равенства  двух выражений, содержащих (предметную) переменную   Множество решений  уравнения  (1) – это множество истинности     предиката (1).

Всякий элемент      называется   решением (корнем)  уравнения (1). Решить  уравнение (1) – значит найти множество истинности    предиката (1).

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

Переход от одного уравнения к другому, равносильному первому, называется равносильным  преобразованием.