рабочая тетрадь 4. Рабочая тетрадь 4!. Рабочая тетрадь 4

Название	Рабочая тетрадь 4
Анкор	рабочая тетрадь 4
Дата	22.11.2022
Размер	94.22 Kb.
Формат файла
Имя файла	Рабочая тетрадь 4!.docx
Тип	Документы #806809

Рабочая тетрадь № 4

Высказывание – это утверждение, которое может принимать два значения: истина, либо ложь.

Если высказывание A ложно, то будем записывать A = 0, иначе A = 1.

Математическая логика не касается вопросов ложности или истинности конкретных высказываний [1]. Здесь высказывания X, Y, Z –переменные, которые могут быть ложными или истинными.

Операции с переменными, принимающими такие значения, называются булевой алгеброй (алгеброй логики).

1. Теоретический материал

Пусть A и B – высказывания. С этими высказываниями можно выполнять следующие основные логические операции:

отрицание «НЕ»: ¬A

конъюнкция «И»: A&B

дизъюнкция «ИЛИ»: A˅B

импликация «следует»: A → B

эквивалентность: A B.

Элементарные логические операции

0

1

0

1

0

0

1

1

0

0

1

1

0

1

0

1

0

1

1

0

0

1

1

0

0

0

1

1

0

1

0

1

1

1

1

0

Приоритет выполнения операций:

Сначала выполняются действия в скобках. Затем выполняется операция отрицания ( ), далее – конъюнкция ( ), дизъюнкция ( ), импликация ( ) и в последнюю очередь – эквивалентность ( ). Однотипные операции выполняются в порядке следования.

Таблица истинности – это набор всевозможных комбинаций переменных с указанием значения логической формулы. Такая таблица, описывает логическую функцию.

2. Пример

Задача:

Приведите таблицу истинности для следующего выражения

B A B

Решение:

A

B

B A

( B A)

( B A B

0

0

1

0

1

0

0

1

1

0

1

1

1

0

0

0

0

1

0

1

1

1

Задача:

Для какого из представленных вариантов символьных строк следующее высказывание является ложным:

(Первая буква гласная) → ¬(Третья буква согласная) ?

1) abedc; 2) babas; 3) becde; 4) abcab.

Решение:

Логическое выражение является импликацией. Данная логическая функция ложна только в том случае, когда из истинной левой части высказывания следует ложная правая часть. Левая часть будет истинной для вариантов один и четыре. Правая часть является отрицанием высказывания «третья буква согласная» (что эквивалентно высказыванию«третья буква гласная»). При этом правая часть ложна для вариантов два, три и четыре. Следовательно, правильный вариант расположен под номером 4.

Ответ:

4

Задача:

Какое из представленных выражений равносильно следующему:

A ∨ ¬(¬B ∧ ¬C) ?

1) ¬A∨¬B∨¬C; 2) A ∧ ¬(B ∧ C);

3) A∨¬B∨¬C; 4) A ∨ B ∨ C.

Решение:

Задействуем законы де Моргана. Раскрыв скобки запишем:

A ∨ ¬(¬B ∧ ¬C) = A ∨ (¬¬B ∨ ¬¬C).

Теперь применим закон двойного отрицания:

A ∨ (¬¬B ∨ ¬¬C) = A ∨ B ∨ C.

Следовательно, правильный вариант четвертый.

Ответ:

4

Задача:

По заданному фрагменту таблицы истинности для выражения F определить, какое из перечисленных ниже логических выражений ему соответствует [5].

X

Y

Z

F

1

0

0

0

0

0

1

1

0

1

0

0

1) ¬X ∧ ¬Y ∧ Z; 2) X ∨ ¬Y ∨ ¬Z;

3) ¬X ∧ ¬Y ∧ Z; 4) ¬X ∨ ¬Y ∨ Z.

Решение:

Подставим представленные значения X, Y и Z из таблицы во все варианты логических функций.

Для первого выражения получим:

¬1 ∧ ¬0 ∧ 0 = 0 ∧ 1 ∧ 0 = 0;

¬0 ∧ ¬0 ∧ 1 = 1 ∧ 1 ∧ 1 = 1;

¬0 ∧ ¬1 ∧ 0 = 1 ∧ 0 ∧ 0 = 0.

Для второго выражения получим:

1 ∧ 0 ∧ ¬0 = 1 ∧ 0 ∧ 1 = 0;

0 ∧ 0 ∧ ¬1 = 0 ∧ 0 ∧ 0 = 0;

0 ∧ 1 ∧ ¬0 = 0 ∧ 1 ∧ 0 = 0.

Для третьего выражения получим:

1 ∨ ¬0 ∨ ¬0 = 1 ∨ 1 ∨ 1 = 1;

0 ∨ ¬0 ∨ ¬1 = 0 ∨ 1 ∨ 0 = 1;

0 ∨ ¬1 ∨ ¬0 = 0 ∨ 0 ∨ 1 = 1.

Для четвертого выражения получим:

¬1 ∨ ¬0 ∨ 0 = 0 ∨ 1 ∨ 0 = 1;

¬0 ∨ ¬0 ∨ 1 = 1 ∨ 1 ∨ 1 = 1;

¬0 ∨ ¬1 ∨ 0 = 1 ∨ 0 ∨ 0 = 0.

Таким образом, сопоставив приходим к выводу, что правильный вариант под номером один.

Ответ:

1

Задача:

Найдите наименьшее целое число x> 0, при котором логическое выражение (4 > –(4 + x) x) → (30 > x ⋅ x) является ложным?

Решение:

Импликация ложна только в случае, если левая часть выражения истинна, а правая ложна.

Рассмотрим левую часть. После преобразований можно записать квадратное неравенство x² + 4x + 4 > 0 или (x + 2)²> 0. Поскольку x> 0, левая часть импликации истинна всегда. Выражение (30 > x⋅x) будет ложным для x > 5. ( 30 > 5², но 30 < 6²). Следовательно наименьшее целое число x большее нуля, для которого высказывание ложно равно 6.

Ответ:

6

Задача:

Перед началом соревнований три зрителя высказали предположения по поводу победителей:

Коля победит, Петя будет вторым;

Петя– третий, Ваня– первый;

Коля будет последним, а первым будет Женя.

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

Решение:

Обозначим буквами предсказания каждого зрителя [5].

Первый: A — Коля победит; B — Петя второй.

Второй: C — Петя третий; D — Ваня первый.

Третий: E — Коля последний; F — Женя первый.

Нетрудно заметить, что истинными одновременно не могут быть выражения B и C; A и E; A и D; A и F; D и F.

Поскольку из условия известно, что в каждом из прогнозов одно высказывание ложно, а другое истинно, то получаем следующее:

A¬B ∨ ¬AB = 1;

C¬D ∨ ¬CD = 1;

E¬F ∨ ¬EF = 1.

Так как все условия должны быть истинными одновременно справедливо следующее выражение:

(A¬B ∨ ¬AB)(C¬D ∨ ¬CD)(E¬F ∨ ¬EF) = 1.

Раскроем скобки. Используя логические законы, рассмотренные ранее, получим:

A¬BC¬DE¬F ∨ ¬ABC¬DE¬F ∨ A¬B¬CDE¬F ∨

∨ ¬AB¬CDE¬F ∨ A¬BC¬D¬EF ∨ ¬ABC¬D¬EF ∨

∨ A¬B¬CD¬EF ∨ ¬AB¬CD¬EF = 1.

Учитывая, что BC = 0, AE = 0, AD = 0, AF = 0, DF = 0, получаем следующее:

¬AB¬CDE¬F = 1.

Представленная конъюнкция равна единице, если все сомножители равны единице, следовательно:

A = 0; B = 1; C = 0; D = 1; E = 1; F = 0.

Вспоминая высказывания каждого из зрителей, получаем, что Петя — второй, Ваня — первый, Коля — последний, т. е. четвертый. Таким образом, Женя на третьем месте. Следовательно, правильный ответ — 3124.

Ответ:

3124

3. Задания

1.

Задача:

Составить таблицу истинности для выражений

1) AvB AB

2) v( ⊕B (⊕ – исключающее ИЛИ, сумма по модулю 2)

3) AvB C

Решение:

A

B

AvB

0

0

0

1

0

0

1

1

0

0

1

0

1

1

0

1

1

1

1

1

A

B

(

v

⊕

0

0

1

1

0

1

1

0

1

0

1

1

1

0

1

0

0

0

1

1

1

1

1

1

0

0

0

1

A

B

C

AvB

0

0

0

0

1

0

0

1

0

1

0

1

0

1

0

0

1

1

1

1

1

0

0

1

0

1

0

1

1

1

1

1

0

1

0

1

1

1

1

1

2.

Задача:

Для какого слова истинно высказывание:

(Первая буква гласная ∨ Пятая буква согласная) → Вторая буква гласная?

1) арбуз; 3) кресло; 2) ответ; 4) привет.

Решение:

В слове «привет» первая буква согласная «п» и пятая гласная «е» => получаем (0 ∨ 0) = 0. Вторая буква в этом слове согласная => (0 ∨ 0) → 0 = 0 → 0 = 1, т.е. выражение истинно

Ответ:

4)привет

3.

Задача:

Выберете логическое выражение эквивалентное следующему:

¬(¬A ∧ B) ∨ ¬C?

1) ¬A ∨ B ∨ ¬C; 2) A ∨ ¬B ∨ ¬C;

3) ¬A ∨ ¬B ∨ ¬C; 4) A ∨ B ∨ ¬C.

Решение:

(по закону де Моргана) ¬(¬A ∧ B) = ¬¬А ∨ ¬В = А ∨ ¬В =>

А ∨ ¬В ∨ ¬C

Ответ:

2)

4.

Задача:

По заданному фрагменту таблицы истинности для выражения F определить какое из перечисленных ниже логических выражений ему соответствует.

X

Y

Z

F

0

0

0

0

1

0

1

1

0

1

0

1

1) X ∧ Y ∧ Z; 2) X ∧ Y ∨ Z;

3) ¬X ∨ Y ∨ ¬Z; 4) X ∨ Y ∧ ¬Z.

Решение:

Ответ:

4

5.

Задача:

Найдите наибольшее целое число x> 0, для которого ложно выражение:

((x + 6) ⋅ x + 9 > 0) → (x ⋅ x > 20) .

Решение:

Для того, чтобы выражение получилось ложным, нам подойдет только один вариант когда 1 → 0 = 0. Чтобы во второй скобке получить 0 выражение хх не должно превышать 20. Наибольшее целое число для этого 4, так как 44=16, а 5*5=25(уже не подойдет)

Ответ:

4

6.

Задача:

Найдите значения логических переменных A, B, C, D, при которых логическое выражение (¬(C∨B) ∧A) → ((¬A∧ ¬C) ∨D) = 0.

Решение:

Для того, чтобы выражение получилось ложным, нам подойдет только один вариант когда 1 → 0 = 0. Чтобы в первой скобке получить 1, нужно чтобы А=1, а C∨B=0. Чтобы во второй скобке получить 0, нужно чтобы D=0 и, так как А=1, то С может быть равно и 1, и 0, но из выражения C∨B=0 делаем вывод, что С=0 и В=0 соответственно.

Ответ:

А=1, В=0, С=0, D=0

7.

Задача:

В соревновании участвовало пять человек: Аня, Надя, Вера, Рита, Саша. Об итогах турнира есть пять высказываний:

1. Первое место заняла Аня, а Рита – третья.

2. Пятая Вера, а вот Надя первая.

3. Первая Саша, а Вера – вторая.

4. Рита пятая, а Надя была четвертой.

5. Надя была четвертой, а первой — Аня.

Известно, что в каждом утверждении только одно утверждение из двух истинно. Требуется найти, кто занял первое место, и на каком месте была Аня? Ответ следует записать в виде первой буквы имени победительницы, и, через запятую, места, занятого Анной.

Решение:

Если исходить из верности утверждения, что Надя была 4,то значит что Рита была не 5 и Аня была не 1 и Надя была не 1, если Аня была не 1,то верно утверждение, что Рита была 3, если Надя не была первой, то верно утверждение, что Вера была 5, раз Вера 5, то верно ,что Соня 1, а значит оставшееся второе место заняла Аня

Ответ:

С,2

Тест 4

1.

Задание:

Таблица, включающая всевозможные значения логической функции, называется:

Ответ:

1) таблица ложности; 2) таблица истинности;

3) таблица значений; 4) таблица ответов.

2.

Задание:

Значение логического выражения ¬(А٧В) по закону Моргана равно:

Ответ:

1) ¬А&¬В; 2) ¬А&В; 3) А&¬В; 4) ¬А٧¬В.

3.

Задание:

Какое из перечисленных имен удовлетворяет истинности высказывания:

¬ (Первая буква согласная → Третья буква гласная) ?

Ответ:

1) Ирина; 2) Сергей; 3) Григорий; 4) Ольга.

4.

Задание:

Выберете выражение эквивалентное следующему:

¬A ∨ ¬(B ∧ C)?

Ответ:

1) ¬A ∨ ¬B ∨ ¬C; 2) ¬A ∧ B ∧ C;

3) A ∧ ¬B ∧ C; 4) (¬A ∨ B) ∧ C.

5.

Задание:

По заданному фрагменту таблицы истинности для выражения F определить какое из перечисленных ниже логических выражений ему соответствует.

X

Y

Z

F

0

0

0

0

1

1

0

1

1

0

0

1

Ответ:

1) ¬X ∨ ¬Y ∨ ¬Z; 2) X ∧ Y ∧ Z;

3) X ∧ ¬Y ∧ ¬Z; 4) X ∨ Y ∨ Z.

6.

Задание:

Для какого из приведенных значений x выражение (x > 2)∨(x > 5)→(x < 3) истинно.

Ответ:

1) 5; 2) 3; 3) 4; 4) 2.

7.

Задание:

Для какого из приведенных значений x выражение

¬((x > 2) → (x > 3)) = 1 .

Ответ:

1) 1; 2) 2; 3) 3; 4) 4.

8.

Задание:

Сколько разнообразных решений имеет выражение

A∧ ¬B∧C∧ ¬D∧ (E∨ ¬E) = 0 ,

A, B, C, D, T — логические переменные?

В качестве ответа требуется написать количество таких наборов.

Ответ:

9.

Задание:

Каково наибольшее целое число X, при котором истинно высказывание

(100 < X ⋅ X) → (100 > (X + 1)(X + 1)) ?

Ответ:

10.

Задание:

Четыре друга — Антон, Михаил, Николай и Виктор пришли в автосалон. Продавец сказал, что осталось только четыре машины: красная, черная, белая и синяя. Каждый из друзей купил по машине. Имеется три утверждения:

Красную машину купил Антон, а черную– Михаил;

Антон взял черный автомобиль, а Виктор – белый;

Николай забрал черное авто, а Виктор — синее.

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

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

Ответ:

Реализация задач на языке программирования Python

1. Теоретический материал

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

В побитовых операторах (операциях) операнды рассматриваются как последовательность бит (нулей или единиц). Над разрядами существует возможность выполнять известные логические операции (логическое «ИЛИ», логическое «И», и т.д.).

Битовые операции в Python в порядке убывания приоритета представлены ниже:

Операции

Назначение

побитовое НЕ (инверсия);

<<,>>

битовые сдвиги влево и вправо;

&

побитовое И;

^

побитовое исключающее ИЛИ (XOR);

|

побитовое ИЛИ (OR).

В битовой инверсии значение любого бита числа меняется на противоположное. У числа при этом меняется знак со смещением на -1.

Операторы сдвига влево << и сдвига вправо >> сдвигают биты на одну или несколько позиций влево или вправо соответственно.

Битовый оператор И (AND) есть бинарным и выполняет побитовое «И» для каждой пары битов операндов, которые размещаются слева и справа от знака оператора &.

Битовый оператор «исключительное ИЛИ» обозначается ^ и выполняет операцию сложения по модулю 2 для любого бита операндов.

Битовый оператор ИЛИ (OR) символом |. Оператор реализует побитовое логическое сложение.

2. Пример

Задача:

Дано число x = 37, y = 58.

Найти x, x>>3, x<<2, x&y, x^y, x|y

Решение (код программы):

x, y = 37, 58

#x в десятичной и двоичной системе

print('x = ', x, ' x_bin = ', bin(x))

#y в десятичной и двоичной системе

print('y = ', y, ' y_bin = ', bin(y))

#x в десятичной и двоичной системе

a = x

print('x =', a, ' x_bin = ', bin(a))

#x>>3 в десятичной и двоичной системе

b = x >> 3

print('x>>3 =', b, ' (x>>3)_bin = ', bin(b))

#x<<2 в десятичной и двоичной системе

c = x << 2

print('x<<2 =', c, ' (x<<2)_bin = ', bin(c))

#x&y в десятичной и двоичной системе

d = x & y

print('x&y =', d, ' (x&y)_bin = ', bin(d))

#x^y в десятичной и двоичной системе

e = x ^ y

print('x^y =', e, ' (x^y)_bin = ', bin(e))

#x|y в десятичной и двоичной системе

f = x | y

print('x|y =', f, ' (x|y)_bin = ', bin(f))

Задача:

Вытянуть из числа 4,5,6 биты и определить их целочисленное значение.

Решение (код программы):

number = int(input('Input number: '))

# фильтр на 4,5,6 биты

number &= 0b1110000

# сдвинуть на 4 разряда вправо

number >>= 4

print('number = ', number)

Задача:

Умножить значения двух чисел. В первом числе взять биты, которые размещенные в позициях 0-5. Во втором числе взять биты, которые размещены в позициях 0-7.

Решение (код программы):

x = int(input('x = '))

y = int(input('y = '))

# фильтр на 0-5 биты

x &= 0b11111

# фильтр на 0-7 биты

y &= 0b1111111

# умножить

**z = x*y

print('x = ', x)

print('y = ', y)

print('z = ', z)

3. Задания

Задача:

Даны два различных числа k и n. Выведите значение 2^k+ 2ⁿ, используя только битовые операции.

Решение (код программы):

k = int(input('Введите k: '))

n = int(input('Введите n: '))

print ('Результат: ',(1<< k) + (1 << n))

Задача:**

Ввести число n > 0 с клавиатуры. Если число n является точной степенью двойки, вывести “YES”, в противном случае “NO”.

Решение (код программы):

n = int(input('Введите n: '))

for i in range (0, 32):

if (n == 2 <
print('YES')

break

else:

print('NO')

Задача:

Даны целые числа a и k. Выведите число, которое получается из а установкой значения k-го бита в 1.

Решение (код программы):

a = int(input('Введите a: '))

n = int(input('Введите n: '))

if (a & (1 << (n - 1)) == 0):

a = a | (1 << (n - 1))

print('Результат: ', a)

Задача*:

Дано целые числа n и k. Обнулите в числе n его последние k бит и выведите результат. Рекомендуется сделать эту задачу без использования циклов.

Решение (код программы):

n = int(input('Введите n: '))

k = int(input('Введите k: '))

n = (n >> k) << k

print('Результат: ', n)