@blkmg

Всем привет, может кто знает хорошие сайты или книги для самостоятельного изучения алгебры логики, посоветуйте пожалуйста(цель научиться решать сложные олимпиадные задачи).

0

@кот Бегемот

Олимпиады по информатике начиная с городского уровня проводятся только и только по программированию. Так что лучше учитесь программировать. Хотя, конечно, алгебру логики знать надо, но всё, в принципе, есть в интернете. Наберите в поиске «Законы алгебры логики» и «Решение задач с помощью законов алгебры логики» и в путь.

0

@blkmg

Да, но вот такая задачка: непонятно что с ней делать, что вообще такое фиктивные переменные?

0

@кот Бегемот

Фиктивные переменные - это такие переменные, которые никак не влияют на значение логической функции. Вот в приведенном примере
ху=F(xy)
00=1
01=0
10=1
11=0
Переменная Х никак не влияет на значение функции: при х=0 и при х=1 мы получили те же самые значения функции, следовательно х здесь просто лишний, то есть переменная как бы есть, но она не нужна, он фиктивна.
Это подтверждается и построением функции по таблице истинности, например, через СДНФ:
неХ*неY+х*неY=неY(неХ+Х)=неY
В преобразованном виде переменная Х исчезла, следовательно, она фиктивная.

Теперь как решать задачу. Здесь существует много способов. Я решал самым примитивным. Записал таблицу истинности. Для этого переведём запись A50F55AA из 16-ричной в двоичную систему:
10100101000011110101010110101010 - это значения функции при записи переменных в лексикографическом порядке (то есть по увеличению), мы их запишем в последний столбец таблицы истинности:

abcde=F(abcde)
00000=1
00001=0
00010=1
00011=0
00100=0
00101=1
00110=0
00111=1
01000=0
01001=0
01010=0
01011=0
01100=1
01101=1
01110=1
01111=1
10000=0
10001=1
10010=0
10011=1
10100=0
10101=1
10110=0
10111=1
11000=1
11001=0
11010=1
11011=0
11100=1
11101=0
11110=1
11111=0

А теперь поанализируем эту таблицу.
Вот первая строка:
00000=1
Если теперь изменить какую либо переменную на 1 и результат изменится, значит эта переменная влияет на функцию и фиктивной он не может быть, если результат не изменится, она может быть фиктивной.
Вот что получилось:
00000=1
----------
10000=0
01000=0
00100=0
00010=1
00001=0
Переменные с номерами 1,2,3 и 5 не могут быть фиктивными, так как при их изменении меняется значение функции.
Следовательно, кандидат у нас один - 4-я переменная.
Её значения чередуются через строчку, например, в первой строке
00000
в третьей строке
00010
Если посмотреть значение функции в этих парах строк (1-3, 2-4,5-7, 6-8 и т.д), увидим, что функция в этих парах не меняется, то есть, от 4 переменной ничего не зависит, она фиктивна.
Как показано выше, остальные переменные фиктивными быть не могут.

Приведенный способ не является оптимальным, уже потому, что с первого раза мы могли и не найти кандидатов на фиктивные переменные.
Правильнее было бы составить СДНФ по таблице истинности и упростить, лишние переменные бы исчезли в процессе упрощения.
Можно было так же отсортировать таблицу пятью способами, например в Excel, тогда у фиктивных переменных совпали бы верхняя и нижняя половины. Возможны и другие способы

PS можно было так же сравнивать значения функции парами
1-2,3-4 и т д для 5 переменной,
1-3,2-4 и т д для 4 переменной
1-5, 2-6 и тд для 3 переменной
1-9, 2-10 и тд для 2 переменной
1-17, 2-18 и тд для 1 переменой,
Но это уже дело вкуса

1

@blkmg

То есть ты просто в интернете искал задачи разной сложности и решал?

0

@кот Бегемот

Ну, мне было проще - мы в школе проходили. Но, в принципе, можно всё сделать самому.

0

@blkmg

А как ты понял что 0000=1 или 0001=0?

0

@кот Бегемот

Я же по-русски объяснял, может тебе на другом языке объяснить?
Почитай ещё раз решение, может, сообразишь.

Вот отсюда:

1