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

равносильные упрощенные формы или равносильные формы, имею­ щие более удобный с некоторых позиций вид. Из соотношений 2) - 6) видно, что операция & напоминает ум­ ножение (обладает некоторыми свойствами умножения), а v - сложе­ ние, поэтому часто конъюнкцию двух высказываний называют (логи­ ческим) произведением их, а дизъюнкцию - (логической) суммой. Битый - правду говорит Молвь люден простых - Стоит двух, кто не был бит, Грамотей — троих. П.-Ж. Беранже § 7. Зависимости между пропозициональными связками Связки 1, V, =>, = не являются независимыми друг от друга в том смысле, что одни из них можно выражать через другие, так что при этом получаются равносильные пропозициональные фор­ мы. Например, связка = может быть выражена через связки и & на основании соотношения А=В ~ {А=>В) & (jS=>^). (1.1) Для доказательства (1.1) достаточно составить таблицы истин­ ности и убедиться, что результирующие столбцы этих таблиц совпа­ дают. Для импликации имеем: A^^B-IAvB. (1.2) Таким образом, связку s можно выразить через 1 , & и v ; А^В~(]Л\/В)&(\ BvA). (1.3) Так как А равносильно 1(1 Л), то А&.В равносильно 1(1^ ) & 1 (15), а последнее согласно закону де Моргана равносильно 1(1^ v l 5 ) , следовательно, 28