Спирина, М.С. Дискретная математика

? Что делать, если одни аксиомы теории и следствия из них будут вы­ полняться в интерпретации х, а другие — нет? Такая интерпретация не может являться адекватным представ­ лением теории, ее моделью. Интерпретация х. F -> L называется моделью формальной теории Т - (A, F, Р, R), если в ней выпол­ няются все теоремы Т. Модель нужна для более простого и нагляд­ ного описания формальной теории, а формальная теория являет­ ся «законодательным актом» существующей модели. Также можно допустить, что одна и та же формула будет вы­ полняться в одной интерпретации, но не выполняться в другой. Понятно, что, например, аксиома не должна допускать подоб­ ные противоположные интерпретации, т. е. для любой интерпре­ тации ее образ должен быть «тождественно-истинным». В гл. 4, где рассматривались булевы функции, такая формула названа тавто­ логией. Обобщим этот термин на формальные системы. Формула / е F формальной теории Т = {A, F, Р, R ) называется общезначи­ мой, или тавтологией, если она выполняется в любой интерпрета­ ции, и противоречивой, если в любой интерпретации ее образ ложен. Если среди теорем формальной теории Т нет противоречивых, т.е. V /e {Л10 1— у/г} 3 jc : v (x ( / ) ) = 1, то формальная теория Т назы­ вается семантически непротиворечивой. Требования, предъявляемые к формальным системам. Итак, для семантически непротиворечивой теории существует описывающая ее модель. Но практически понятием семантической непротиво­ речивости пользоваться трудно. Должен быть однозначный крите­ рий, служащий инструментом выявления непротиворечивости. Им служит понятие формальной непротиворечивости. Формальная те­ ория Т называется формально непротиворечивой, если в ней не являются одновременно выводимыми формула / и ее отрицание. Такое определение непротиворечивости соответствует аристотеле­ вой логике и является обывательски более понятным. Инструмен­ том же практического применения этих понятий служит следую­ щее утверждение: формальная теория семантически непротиворечи­ ва тогда и только тогда, когда она формально непротиворечива. Итак, формальная и семантическая непротиворечивость теории выпол­ няются или не выполняются одновременно, поэтому далее будем просто употреблять словосочетание «непротиворечивость теории». Также необходимыми свойствами формальных систем являют­ ся их полнота и независимость. Рассмотрим отдельно каждое из требований, накладываемых на формальную систему. Они назы­ ваются критериями. Непротиворечивость формальной системы S означает, что в ней нельзя из некоторого набора аксиом вывести одновременно два противоречивых суждения А и А, что соответствует одному из 213