Математическая логика и теория алгоритмов

чать некоторое высказывание. Истинностное значение полученного высказывания можно определить с помощью таблиц истинности. Так как добавление каждой новой пропозициональной буквы увеличивает количество строк в таблице истинности вдвое, то пропо­ зициональная форма, содержащая п различных пропозициональных букв, имеет таблицу истинности с 2" строками. Например, для формы ({{A&B)\fC)=i'A) имеем следующую таблицу истинности: А В с {Л&В) ((A&B)vQ (((AAB)vC)^A) Л Л л л л И Л л и л и Л Л и л • л л и Л и и л и л И л л л л и И л и л и и И и л и и и И и и и и и Составление таблицы истинности можно сократить, выписывая шаг за шагом под каждой пропозициональной связкой истинностные значения той составляющей пропозициональной формы, для которой применяется эта связка. Например, для той же формы (((A&B)vQ=pA) получаем таблицу: А в с (((А&В) V С) =>А) Л л л л л и л л и л и л л и л л л и л и и л и л и л л л л и и л и л и и и и л и и и и и и и и и Следующий метод построения таблиц истинности называют ал­ горитмом Квайна. В форме выбирается некоторая буква, например, та, которая чаще всего встречается в рассматриваемой форме. Выбранной букве (для формы D=(((^&i5)vC)=>^) это будет буква А) 19