 | Эта статья требует дополнительных ссылок для проверки . ( ноябрь 2012 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
В логике две формулы равно выполнимы, если первая формула выполнима всякий раз, когда выполняется вторая, и наоборот; другими словами, либо обе формулы выполнимы, либо обе нет. [1] Равно выполнимые формулы могут не совпадать, однако, для определенного выбора переменных. В результате равная выполнимость отличается от логической эквивалентности , поскольку две эквивалентные формулы всегда имеют одни и те же модели.
Равно выполнимость обычно используется в контексте перевода формул, чтобы можно было определить перевод как правильный, если исходная и полученная формулы равнозначны. Примерами переводов, включающих это понятие, являются сколемизация и некоторые переводы в конъюнктивную нормальную форму .
Примеры [ править ]
Перевод из логики высказываний в логику высказываний, в которой каждая бинарная дизъюнкция заменяется на , где - новая переменная (по одной для каждой замененной дизъюнкции), представляет собой преобразование, при котором выполняется выполнимость: исходная и результирующая формулы равно выполнимы. Обратите внимание, что эти две формулы не эквивалентны: первая формула имеет модель, в которой истинно, а ложь (значение истинности модели, не имеющее отношения к значению истинности формулы), но это не модель второй формулы. , в котором должно быть истина в этом случае.
Ссылки [ править ]
- ^ М. Krötzsch (11 октября 2010). Описание Логические правила . IOS Press. ISBN 978-1-61499-342-1.
 | Эта статья по математической логике - незавершенная . Вы можете помочь Википедии, расширив ее . |
