Структуры данных и модели вычислений
Рассматриваемая нами формула является теперь
- — произведение чисел ,
- — число, обратное числу ,
- — "".
Рассматриваемая нами формула является теперь утверждением о том, что для любых двух чисел из нашего универсума выполняется равенство
Очевидно, что это утверждение истинно. Нетрудно привести примеры интерпретаций, при которых наша формула ложна. Следующие примеры показывают, что существуют формулы, тождественно истинные, то есть истинные при любой интерпретации, а также тождественно ложные.
Примеры. Пусть и — одноместные предикатные символы.
- — тождественно истинная формула.
- — тождественно ложная формула.
- — истинность этой формулы зависит от интерпретации предикатных символов и .
Если в формуле есть свободные переменные, то она получает конкретное истинностное значение при означивании этих переменных.
Формула называется выполнимой, если она истинна хотя бы при одной интерпретации.
Две формулы называются логически равносильными, если при любой интерпретации предикатных и функциональных символов и при любом означивании свободных переменных они имеют одно и то же истинностное значение.
Например, формулы
не являются логически равносильными, а формулы
логически равносильны.
Логическую равносильность формул будем обозначать знаком , например,
Заметим, что в этом выражении фигурирует не одна формула, а две, соединенные знаком логической равносильности.
