Пусть минимальный клон P
 Скачать 77.14 Kb.
|
|
1 Задача 2 Пусть минимальный клон P 2 состоит из двух функций, отличных от тож- дественной. Пусть это функции f и g. Тогда по свойству [J k ? {f }] = A =? g ? [J k ? {f }] , значит каждая из этих функций должна давать в замыкании множество функций, содержащее другую. При этом тождественная функция должна содержаться в минимальном клоне только, если ее нельзя вывести из других функций. Рассмотрим функции одной переменной и соответствующие им минимальные клоны: 0 ? [{x, 0}] 1 ? [{x, 1}] x ? [{x}] = J 2 Ї x ? [{Ї x}] Получили всего 3 минимальных клона. Их комбинации: [{Їx, 0, 1}] = [{Їx, 0}] = [{Ї x, 1}], [{x, 0, 1}] - не минимальные клоны с точки зрения описания, хотя первая группа подходит по определению минимального клона. Функции двух переменных: x ? y ? [{x ? y}] x ? y ? [{x ? y}] Другие функции двух переменных в замыкании вместе с тождественной функцией дают константы, а из констант сами не выводятся. К примеру, с суммой по модулю два, получаем константу 0, из которой не можем в замыкании с тождественной функцией вывести саму функцию суммы по модулю два, значит это не минимальный клон. Еще нужно рассмотреть функции трех переменных, потому что там есть функция голосования, у которой интересные свойства. xy ? yz ? xz. Она будет давать минимальный клон - тождественная функция - это отож- дествление всех переменных, отождествив только две переменные, полу- чим после преобразования опять же тождественную функцию, так что ничего другого в замыкании мы не получим, значит это минимальный клон. Еще возникла идея как-нибудь подправить сумму по модулю два - если 1 брать сразу 3 слагаемых, то при отождествлении мы получим тожде- ственную функцию, а не константу, значит она тоже подойдет. Рассматривая другие функции трех переменных над P 2 , нужно смотреть на то, чтобы при отождествлении любых переменных сразу получалась тождественная функция. Но таких больше нет - получим либо констан- ту, либо отрицание, либо какую-нибудь функцию двух переменных, а из этого нельзя будет вывести изначальную функцию. Для функций от 4 переменных или более по теореме 10.1 минимальных клонов в P 2 не будет. Итого 7 минимальных клонов - тождественная с 0, тождественная с 1, отрицание, дизъюнкция и конъюнкция, голосование и сумма трех по мо- дулю два. 2 Задача 3 В теореме 10.1 дана классификация минимальных клонов. Первая груп- па - это функции одной переменной. Их в 11-значной логике 11 11 1 = 285311670611 > 40000000 . Таким образом, даже если взять все мини- мальные клоны, порожденные функциями одной переменной в P 11 , их уже будет существенно больше 40 миллионов. 2 |