После выполнения шага 1 на столе лежит яблоко, которое достали из корзины первым, а вторая корзина пуста. После каждого выполнения шага 2 большее яблоко перемещается в корзину, а меньшее остается на столе. В результате на столе окажется самое маленькое яблоко.
При обосновании корректности циклических алгоритмов полезно использовать понятие инварианта цикла. В случае приведенного алгоритма инвариантом цикла является такое условие «лежащее на столе яблоко — самое маленькое из всех взятых до сих пор». В начале алгоритма условие очевидно выполняется (любое яблоко удовлетворяет этому условию). Условие остается истинным на каждом шаге в соответствии с приведенными правилами. Таким образом, в конце алгоритма, когда все яблоки взяты, получим самое маленькое яблоко из всех.
F = X ∨ ¬Y
Объяснение:
F = X v ¬(X -> Y) & ¬(Z) & ¬(Y) v ¬(Y & ¬(X & Z))
Заменим знаки операций более привычными и тогда будет проще.
F = X + ¬(X -> Y) * ¬Z * ¬Y + ¬(Y * ¬(X * Z))
Операцию импликации замени эквивалентом
F = X + (¬X + Y) * ¬Z * ¬Y + ¬(Y * ¬(X * Z))
Выражение (¬X + Y) * ¬Z * ¬Y равно ¬X * ¬Y * ¬Z из-за Y * ¬Y = 0.
К выражению ¬(Y * ¬(X * Z)) применим правило де-Моргана:
¬Y + X*Z. Получаем
F = X + ¬X * ¬Y * ¬Z + ¬Y + X*Z;
X + X * Z = X(1 + Z) = X, тогда
F = X + ¬Y * (¬X * ¬Z + 1) = Х + ¬Y, или в прежних обозначениях
F = X ∨ ¬Y
