Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

38. Докажите, что только через &и v нельзя выразить отрицание. 39. Исключающее «или» для А и В определяется: {А&^) v Покажите, что эта операция коммутативна и ассоциативна. 40. Следующие формы приведите к д.н.ф. и к.н.ф.: а) А^((А^В)^В)', б) ((A^B)&(C^D))&((A&C)^(^C&D)); в) (А^В)^((А&С)^(А&С)); г) (А^(В&С))&((А^В)&(А^)); д) ((А^В) v(A^C)) А А vC)). 41. Для заданных форм: 1) найдите д.н.ф., к.н.ф.; 2) выясните, является ли заданная форма выполнимой или тавтологией; 3) найдите с.д.н.ф и с.к.н.ф.: а) А=В vC; б) (А^ -пВ) &С; в) (А=А=А=В)&С; г) (А^А^А^В) vC; fl)A=A=BvC', о) (А^В)^>С^—А. 42. Положим, что пропозициональные буквы вместо значений И и Л принимают значения 1 иО соответственно. 1) Из определений операций убедиться, что: а)А&В= тт{А,В); Q)AvB= тах(Л,в); ъ)А^В = min(l, \-А+В). 2) Запишите аналогичную форму для вычисления значений формы А= В, когда ^ и 5 принимают значения О и 1. 43. Составьте программу на любом алгоритмическом языке языке (Pascal, С, С+, С++ или другой язык) для построения таблицы истинности форм: a)A&Bv^C; Q)^vB&C; b)^&^УС; Т) A&BV^C. 44. Составьте программу на любом алгоритмическом языке языке (Pascal, С, С+, С++ или другой язык) для построения с.д.н.ф. следующих форм. Предусмотреть возможность, что с.д.н.ф. может не существовать. В этом случае программа должна напечатать, что данная форма с.д.н.ф. не имеет. a)A&Bv^C; 6)^vB&^C; B)^&BVC; Т) A&(BV^C). 45. Составьте программу на любом алгоритмическом языке (Pascal, С, С+, С++ или другой язык) для построения с.к.н.ф. форм из задачи 44. Предусмотреть возможность, что с.к.н.ф. может не существовать. В этом случае программа должна напечатать, что данная форма с.к.н.ф. не имеет. 46. Составьте программу на любом алгоритмическом языке языке (Pascal, С, С+, С++ или другой язык) для выяснения равносильности форм А и В: а)А=А vB&-nC, В = ^ vB&-nC; б) Л = -А&В vC; В= А&{В v-^C). Программа должна напечатать, равносильныЛ и в или нет. 26