Дискретная математика

57 Например, для формулы (((xtS:y)vz)=>x) имеем следующую таблицу истинности. X У Z (х&у) {(х&у) vz) (((x&y)vz)=>x) 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 1 0 1 0 0 0 0 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 I 1 I 1 Составление таблицы ист1шности можно сократить, вьшисывая шаг за шагом под каждой операцией значения той составляющей формулы, для которой применяется' эта операция. Например, для той же формулы (((х&у) vz)=^x) получаем таблицу; X у Z ({(х & у) vz) ^х) 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 1 0 1 0 0 0 0 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 Следующий метод построения таблиц истинности называют алгоритмом Квайна. В формуле выбирается некоторая переменная, например, та, которая чаще всего встречается в рассматриваемой формуле. Выбранной переменной (для формулы D=(((x&y)vz)=^ х) это будет переменная х) приписывается значение 1 либо 0. Далее проводят вычисления, где возможно, при выбранном значении этой переменной. Если х=1, то для формулы D=(((x&y)vz)=> х), вне зависимости от значении у я z, легко получить, что D=l. При х=0 и z=0 получим снова, что D=l. Наконец, если x=Q и z=l , то D —Q. В результате получим сокращенную запись таблицы истинности, содержащую всего три строки (в данном случае результат не зависит от значений переменной у):