Преобразование логических выражений презентация

Задание B18
Преобразование логических выражений

На прошлом занятии мы разобрали:
Множества
((x ∈ P) → (x ∈ A)) ∨ (¬(x ∈ A) → ¬(x ∈ Q))
y
((x < A) → (x2 < 100)) ∧ ((y2 ≤ 64) → (y ≤ A))

Сегодня мы разберем
¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 4))
x&25 ≠ 0 → (x&17 = 0 → x&А ≠ 0)

Задание 1

Решение
A – A, 15 – P, 18 – Q:
(A^¬P)->(QvP) = ¬(A^ ¬P)vQvP= ¬A v P v Q v P = ¬A v P v Q = 1
A = P = 15

Задание 2

Решение
18 – P, 21 – Q, A – A
¬P->(¬ Q-> ¬ A) = P v (Q v ¬ A) = P v Q v ¬ A = 1
A = P = 18

Задание 3

Решение
A – A, P – 6, Q – 3
¬A^P-> ¬Q = ¬(¬A^P)v¬Q = A v ¬P v ¬Q
A = P = 6

Задание 4
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».
Для какого наибольшего натурального числа А формула
¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 4))
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?

Решение
Введём обозначения A = ДЕЛ(x, А), P = ДЕЛ(x, 6) и Q = ДЕЛ(x, 4)
Введём множества:
A — множество натуральных чисел, для которых выполняется условие A
P — множество натуральных чисел, для которых выполняется условие P
Q — множество натуральных чисел, для которых выполняется условие Q

Решение
A+ ¬P+ ¬Q
A должно покрыть то, что не покрывает ¬P+ ¬Q, то есть ¬(¬P+ ¬Q)
= P*Q
это множество всех чисел, которые делятся одновременно на 4 и 6 (все числа, кратные 4 и 6), то есть, 12, 24, 36 и т. д. (заметим, что 12 — это наименьшее общее кратное чисел 4 и 6). Для того, чтобы перекрыть эти числа, можно выбрать в качестве A любой делитель числа 12, то есть, 1, 2, 3, 4, 6 или 12; наибольшее из этих чисел — 12.

Задание 5
Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14&5 = 11102&01012 = 01002 = 4.
Для какого наименьшего неотрицательного целого числа А формула
x&25 ≠ 0 → (x&17 = 0 → x&А ≠ 0)
тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной х)?

Решение
¬Х → (Y → ¬Z) = Х + (Y → ¬Z) = Х + ¬Y + ¬Z = X + ¬(YZ) = YZ → X
Имеем импликацию Y17ZA → X25 или Y(17 or A) → Z25. Запишем число 25 в двоичной системе счисления: 2510 = 110012. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поскольку 1710 = 100012, двоичная запись искомого числа А должна содержать единичный бит в третьем разряде (как обычно, считая справа налево, начиная с нуля).
Тем самым, наименьшее А = 10002 = 810.

Задание 6
Для какого наименьшего неотрицательного целого числа А формула
x & 29 ≠ 0 → (x & 12 = 0 → x & А ≠ 0)
тождественно истинна (то есть принимает значение 1 при любом неотрицательном целом значении переменной х)?

Решение
¬Х → (Y → ¬Z) = Х + (Y → ¬Z) = Х + ¬Y + ¬Z = X + ¬(YZ) = YZ → X.
Имеем импликацию Z12ZA → Z29 или Z(12 or A) → Z29. Запишем число 29 в двоичной системе счисления: 2910 = 111012. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поскольку 1210 = 011002, двоичная запись искомого числа А должна содержать единичные биты в нулевом и четвертом разрядах (как обычно, считая справа налево, начиная с нуля).
Тем самым, наименьшее А = 100012 = 1710.

Задание 7

Решение
Имеем импликацию Z17ZA → Z28Z45 или Z(17 or А) → Z(28 or 45). Поскольку 2810 = 111002, 4510 = 1011012, для побитовой дизъюнкции имеем: 28or45 = 111101. Тогда Z(17 or А) = Z61.
Импликация принимает вид Z(17 or A) → Z61. Единичные биты двоичной записи числа 61, должны являться единичными битами левой части. Поэтому в побитовой дизъюнкции 17orA единицы должны стоять на нулевой, второй, третьей, четвертой и пятой позициях (как обычно, считая справа налево, начиная с нуля). Запишем числа 17, А и 61 в двоичной системе счисления, и выясним, что наименьшее число, дающее при поразрядной дизъюнкции единицы на указанных позициях:
17: 010001
A: 1?110?
61: 111101
В записи наименьшего числа, дающего при поразрядной дизъюнкции с числом 17 единицы в необходимых разрядах, на месте знаков ? должны стоять нули. Тем самым, искомым числом является А = 1011002 = 4410.
Ответ: 44.

Задание 8
Для какого наименьшего неотрицательного целого числа А формула
x&51 = 0 ∨ (x&41 = 0 → x&А = 0)
тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной x)?

Решение
Х + (Y → Z) = Х + (¬Y + Z) = Х + Z + ¬Y = Y → (X + Z) = (Y → X) + (Y → Z).
Заметим, что первое слагаемое логической суммы является импликацией Z41 → Z51, которая не является истинной для всех х (см. ниже). Тогда необходимо и достаточно, чтобы второе слагаемое логической суммы было тождественно истинным.
Действительно, например, для х = 2 поразрядная конъюнкция с числом 41 дает 0, а с числом 51 дает 2. Поэтому импликация (2&41) → (2&51) принимает вид 1 → 0 — ложь.
2: 000010
41: 101001
2&41: 000000, то есть 2&41 = 0. Высказывание 2&41 = 0 истинно.
2: 000010
51: 110011
2&51: 000010 = 2, то есть 2&51 = 2. Высказывание 2&51 = 0 ложно.
Итак, импликация Z41 → ZA должна быть тождественно истинной. Запишем число 41 в двоичной системе счисления: 4110 = 1010012. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поэтому в правой части единичными битами независимо друг от друга могут быть (а могут не быть) только нулевой, второй и четвертый биты (как обычно, считая справа налево, начиная с нуля). Поскольку искомое A — наименьшее неотрицательное целое число, в его записи нет единичных битов.
Тем самым, наименьшее А = 0000002 = 010.

Задание B10+
Комбинаторика LevelUp

Размещения с повторениями
Размещениями с повторениями называются упорядоченные выборки, содержащие k элементов из данных n элементов, причем каждый элемент исходной совокупности может участвовать в размещении несколько раз.
Формула для расчета количества размещений с повторениями

Размещения с повторениями
На световой панели в ряд расположены 4 лампочки, каждая из которых может гореть красным, жёлтым или зелёным цветом. Сколько различных сигналов можно передать с помощью панели (все лампочки должны гореть, порядок цветов имеет значение)?

Размещения с повторениями
3^4=81

Перестановки с повторениями
Пусть в исходную совокупность входит n1 элементов первого типа, n2 - второго типа, …, nk – k-го типа, при этом n1 + n2 + …+ nk = n. Всевозможные упорядоченные выборки, составленные из всех данных n элементов, называются перестановками с повторениями.
Формула для расчета количества cочетаний с повторениями

Перестановки с повторениями
На световом табло в один ряд располагаются шесть лампочек. Сколько различных сигналов можно получить, имея две зеленые и четыре красные лампочки? Все лампочки должны гореть.

Перестановки с повторениями
Заметим, что все лампочки исходной совокупности должны располагаться на табло (4 + 2 = 6). Так как «все лампочки должны гореть», то сигналы будут отличаться только порядком цветов. Значит, комбинаторная схема – перестановки с повторениями.

Сочетания с повторениями
Сочетаниями с повторениями называются неупорядоченные выборки, содержащие k элементов из данных n элементов, причем каждый элемент исходной совокупности может участвовать в сочетании несколько раз.
Формула для расчета количества сочетаний с повторениями

Сочетания с повторениями
Для составления некоторого кода используются цифры 1, 2, 3. Кодовые слова должны удовлетворять следующим свойствам:
1) Длина кодовых слов равна 3;
2) Кодовые слова могут содержать одинаковые цифры;
3) Кодовые слова, отличающиеся только порядком цифр, считаются одинаковыми.
Сколько вариантов кодовых слов можно составить?

Сочетания с повторениями
Поскольку длина кодовых слов равна 3, то выборки из 3 по 3. Определим комбинаторную схему: из пункта 3 следует, что выборка неупорядоченная при этом «Кодовые слова могут содержать одинаковые цифры», значит, выборки – сочетания с повторениями.
Действительно, таких кодовых слов ровно 10:
111
112 113
122 123 133
222 223 233 333

Задание 1
Вася составляет 5-буквенные слова из четырехбуквенного алфавита {A, C, R, T}, причём буква А используется в каждом слове ровно 2 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом, считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Решение
Варианты размещения двух букв А
Оставшиеся три буквы = 3^3 = 27
Всего вариантов 10*27=270

Задание 2
а) Из класса, в котором учатся 30 человек, нужно выбрать двоих школьников для участия в математической олимпиаде. Сколькими способами это можно сделать?
б) Сколькими способами можно выбрать команду из трех школьников в том же классе?

Решение

Задание 3
На плоскости отмечено 10 точек так, что никакие три из них не лежат на одной прямой. Сколько существует треугольников с вершинами в этих точках?

Решение

Задание 4
Рота состоит из трёх офицеров, шести сержантов и 60 рядовых. Сколькими способами можно выделить из них отряд, состоящий из офицера, двух сержантов и 20 рядовых?