Задачи по дискретной математике

Министерство образования Российской федерации Донской государственный технический университет

Кафедра «Высшая математика»

Задачи по дискретной математике

Ростов-на-Дону 2001

УДК 517 Составители: Баранов И. В. , Глушкова В.Н., Ларченко В.В. Задачи по дискретной математике./ ДГТУ, Ростов-на-Дону, 2001, 16 с.

Задания охватывают различные разделы исчисления высказываний математической логики. Предназначены для студентов всех специальностей, на которых изучается курс дискретной математики. Печатается по решению методической комиссии факультета «Автоматизация и информатика»

© Издательский центр ДГТУ, 2001

2

1.Составить таблицы истинности для формул. 1. ( A → B) ↔ ( A ∨ B)

16. ( A → B ∨ C ) ∧ A ∧ C → A

2. A ↔ B

17. ( A → B ) ∧ ( C → D)

3. A → B

18. ( A → B ) ↔ ( B ∧ C) ∨ A

4. A ∨ B

19. A → ( B ∧ C ) ↔ ( A ∨ B ) ∧ ( A ∨ C )

5. B ↔ A

20. ¬( A → ( B ∧ A)) → A ∨ C

6. A ∨ B

21. A ∧ ( B → A) → A

7. A ↔ B

22. ( A ∧ B → B) → ( A → B )

8. A → B

23. A ∧ ( B ∨ A ) ∧ ( B → A) ∨ B

9. ( A ∧ B ) → B

24. ( A → B ) ∧ A → B

10. ( A ∨ B ) → A

25. A ∧ B → A ∨ B

11. A → A ∨ B

26. A → B ↔ A ∨ B

12. ( A ∨ B ) ∧ ( A ∨ B )

27. A → ¬( B ∨ C)

13. (( A ∧ B ) → C) ↔ ( A → ( B ∨ C))

28. A → ( A → B )

14. A → ( B ∨ C) ↔ ( A → B) ∨ ( A → C )

29. ( A ∨ B → C ) → A

15. ( A ∧ B ) ↔ ( B ∧ C )

30 B → A

2. Установить эквивалентность формул с помощью таблиц истинности . 1. A ∨ B ∧ C и ( A ∨ B ) ∧ C

16. A ↔ B и A ↔ B

2. A ∨ B и A ∧ B

17. ( A ∨ B ) ∧ B и A

3. A → B и A ∨ B

18. A ∨ ( A ∨ B ) и A

4. A ↔ B и ( A ∨ B ) ∧ ( A ∨ B )

19. A ∨ ( A ∨ B ) и A

5. A ↔ B и ( A ∧ B ) ∨ ( A ∨ B )

20. A ∧ ( A ∨ B ) и В

6. A ∧ B и A ∧ B

21. A ∧ ( A ∨ B ) и A

7. A ∨ B и A → B

22. A ∧ ( A ∨ B ) и В

3

8. A ∧ B и A ∨ B

23. ( A ∧ B) ∨ ( A ∧ B ) и A

9. A ∨ B и A ∨ B

24. ( A ∨ B ) ∧ ( A ∨ B) и A

10. A ↔ B и ( A → B ) ∧ ( A → B )

25. ( A ∧ B ) ∨ ( A ∨ B ) и A

11. A ↔ B и ( A → B ) ∧ ( A → B )

26. ( A ∨ B ) ∧ ( A ∨ B ) и B

12. ¬ ( A ↔ B) и ( A ∧ B) ∨ ( A ∧ B)

27. A ∧ B ∨ C ∧ B и B ∧ A ∧ C

13. ( A ∨ B) ∧ ( A ∨ B) и ( A ∨ B) ∧ ( A ∧ B)

28. A ∧ ( A ∨ B) и A ∧ B

14. ( A → B) ∧ ( A → B) и ( B → A) ∧ ( B → A)

29. A ∨ A ∧ B и A ∨ B

15. ( A ↔ B) и ( A ↔ B)

30. A ∨ B и A ∧ B

3. Упростить формулы.

1. (( p → q) → p ) → p 2. ( A1 → A2 ) ∧ ( A2 → A3 ) → ( A3 → A1 ) 3. ( A1 ∧ A3 ) ∨ ( A1 → A3 ) ∨ ( A2 ∧ A3 ) ∨ ( A1 ∧ A2 ∧ A3 ) 4. ¬(( A → B) ∧ ( B → A) 5. A ∨ ¬( B ∧ C ) ∨ ¬( A ∨ B ∨ C ) 6. ( A → B ) → ( B ↔ A) 7. ( A → B ∧ A) ∨ B 8. A1 ∧ A2 ∧ ( A3 ∨ A3 ) 9. A1 ∨ ( A2 ∧ A1 ) 10. A2 ∧ ( A1 ∨ A2 ) 11. ( p ∨ q ∨ r ) ∧ ( p ∨ q ∨ r ) 12. ( r ∨ s ∨ t ) ∧ r ∧ ( p ∨ s ∨ t ) 13. s ∨ ( t ∧ s ∧ m) 14. ( t ∨ r ∨ q ) ∧ ( s ∨ s ) 15. q ∧ ( p ∨ q ) ∧ p 16. q ∨ ( p ∨ p ) ∨ ( p ∨ r ) ∨ s

4

17. m ∧ ( p ∨ m ∨ s) ∧ t ∧ ( t ∨ q ) 18. (d ∨ a d ∨ a) ↓ d 19. p ∧ ( p ∧ q ) 20. c ∨ c ∧ b ∨ c ∨ a 21. (( p ∨ q ) ∧ r ) ∧ ( s ∨ r ) ∧ ( p ∨ q ∨ r ) ∧ t ∧ t 22. ( r ∧ s ∧ t ) ∨ ( r ∧ t ∧ s) ∨ s 23. ( p → q ) ∨ ( p → ( q ∧ p)) 24. p → ( q ∧ p) → p ∨ r 25. p ∧ ( q → p) → p 26. p ∧ ( q ∨ p ) ∧ (( q → p) ∨ q ) 27. r ∨ ( p ∨ p ) ∨ ( q ∧ q ) 28. r ∨ q → ( q ∨ t ) 29. p ∧ q ∧ ( s → ( s ∨ t ))

30. ¬( A1 → A2 ) ∨ ( A2 → A1 ) 4. Записать формулы в ДНФ и СДНФ. 1. ( A → B ) → C

16. ( A → ( A ↔ B)) ∧ C

2. ( A ∨ B ) ∧ ( C ∨ D)

17. A ∧ ( B ∧ C )

3. ( A ∧ B ) ∨ ( C ∧ D) → C

18. A ∨ B → C ∧ A

4 ( A ∧ B) ∨ C

19. ( A → B) ↔ ( A ∨ B)

5. A ∧ B ∨ C ∧ B

20. (( A → B ) ∧ C ) ∨ A ∧ B

6. A ∧ B ∨ C

21. A ∧ B → ( B ∧ B → C )

7. A ∧ B → C

22. ( A ∧ ( A ∨ B )) ∧ ( B → A)

8. AB ↔ A ∨ A ∧ B

23. A ∨ B → C ∧ B

9. ( A ↔ B) ∧ ( A B ∨ AB)

24. A ∧ B → ( A → B)

5

10. A ∨ B → ( A → B)

25. A ∨ B → ( A ↔ B)

11. ( A → B) ∧ (C → B)

26. A ∨ B ↔ A

12. A ∧ ( A → B)

27. A ∧ B ↔ A

13. ( A → B) → ( B → A)

28. ( A ∨ B)( A ∧ B)

14. A ∨ B → C ∧ B

29. ( AB)( A ∨ B)

15. ( A ↔ B) → C

30. ( A ∧ B ) ∨ C

5. Записать формулы в приведенном виде (содержащем только операции ¬, ∧, ∨ над простыми переменными). 1. A ∨ B ∨ C ∨ D

16. ( A ∧ B ) ∧ ( C ∧ D) ∧ C

2. A → ( B ↔ C )

17. A ∧ ( B ∨ C ) → D

3. ( A → A ∧ B) ∧ C

18. A ∧ ( A → B ) → B

4. ( A → B ) ∧ ( C → D) ∧ B

19. ( A ∧ B ) → C

5. ( A → B ) ∧ ( C → D) ∧ D

20. A ↔ B ∧ C

6. ( A ∧ B ∧ C ) → ( A ∨ B ) → B ∧ C

21. ( A ∧ B ) ∧ ( C ∧ D)

7. ( A → B ) ∨ ( C ∨ D)

22. A ∧ B ∧ C ∧ D

8. ( A → B ) ∧ ( B → C )

23. A ∨ B ∨ C ∨ D

9. A ↔ B ∨ A

24. ( A ↔ B) ∧ ( A ∧ B)

10. A → ( B ↔ C )

25. ( A → B) → ( A → B)

11. ( A → B) → A

26. AB ∨ ( A → B ) ∧ A

12. ( A → B) ∧ ( B → C )

27. ( A ∧ B → C ) → ( A → ( B → C ))

13. ( A ∧ B) ∨ ( A → B)

28. A ∧ ( A → B) ∧ ( A → B)

14. A ∨ B → C ∨ A

29. A ∨ B → B ∨ A

15. ( A → B ) → C

30. A → B ∨ C

6

6. Построить полином Жегалкина для функций. 1. f = (00101101)

16. ( x ↔ y ) ∧ ( y ↔ z )

2. ( x1 ↓ x2 ) | x3

17. x ↔ y ↔ z

3. ( x1 → x2 ) ↔ ( x2 ↔ x3 )

18. x ∧ y ↔ x ∧ z

4. ( x1 → x 3 )( x2 ⊕ x3 )

19. ( x → y ) ∨ ( x ∨ y )

5. x1 x3 ∨ x2 x3

20. x ∨ y

6. ( z1 ↔ z2 ) → z3

21. x → y → x → z

7. f = (10101100)

22. ( x ↔ y )( y ↔ z )

8. f = (11000100)

23. ( x ↔ y )( y ↔ z )

9. (x3 ⏐ x2 ) ↓ x3

24. ( x → y ) ↔ ( z → ( x ↔ z ))

10. x → ( x → y )

25. ( x ↔ y ) → ( y → z )

11. ( x ∨ y ) ∧ x → y

26. ( x ↔ y ) ∧ ( y ↔ z )

12. x → y

27. ( x → y )

13. ( x ∨ y ) → ( x ∨ z )

28. ( x ∧ y )( x → y )

14. x ∧ y → ( y → x)

29. ( x ∨ y )( x ↔ y )

15. ( x ∨ y ) ↔ ( x → z )

30. x ↔ y

7. Проверить самодвойственность функций.

1. ( x1 ∨ x2 ∨ x3 ) x4 ∨ x1 x2 x3

16. x1 ⊕ x2 ⊕ 1

2. x1 x 2 ⊕ x1 x 3 ⊕ x 2 x 3

17. (1010)

3. ( 0001001001100111)

18. x1 x2 ∨ x2 x3

4. ( x1 ∨ x 2 )( x1 ∨ x 3 )( x 2 ∨ x 3 )

19. (0101)

5. ( x1 x 2 ) ↓ x 2

20. x1 ⊕ x2 ⊕ x3

6. (01010101)

21. x1 ⏐ x2

7

7. (10101010)

22. x1 x2 ∨ x3

8. xy ⊕ yz

23. x → y

9. x → y ∨ z

24. (10001110)

10. (1001001100110110)

25. x1 → x2

11. xy ∨ y ∨ z

26. x1 ⊕ x2 x1

12. (10101000)

27. (0011)

13. x ↓ y ∨ x → y

28. x1 → x2

14. (1010111100001010)

29. (1100)

15. x1 x2 ⊕ x2 x3

30. ( x1 → x 2 ) → x1 x 3

8. Проверить монотонность функций. 1. x1 → ( x 2 → x 3 )

16. (0011)

2. ( 00110111)

17. xz ( x ⊕ z )

3. x1 x 2 ⊕ x1 x 3 ⊕ x 2 x 3 ⊕ x1

18. x → y

4. (01100111)

19. x ↔ y

5. x ∨ y

20. x → yz

6. ( x → y ) ∨ xy

21. (1100)

7. (10011100)

22. x ⏐ y

8. (0000)

23. (00011100)

9. x ↔ y

24. ( x ∨ y ) z

10. ( x → y ) ∨ z

25. (00101111)

11. (00110111)

26. ( x ⏐ y ) → x ⊕ z

12. ( x ↔ y ) ∧ xy

27. x ∨ y ∨ z

13. xy ⊕ yz

28. ( x ∨ y ) ⊕ z

14. x ∨ y

29. x ⏐ y

15. x → y

30. (1011)

8

9. Проверить полноту следующих систем.

1. {x1 → x2 , x1 → x2 x3}

16. {x1 ⊕ x2 , x2 , x1 ∨ x2 }

2. { ∨ ,∧}

17. {x1 x 2 , x1 ∨ x 2 , x1 → x 2 }

3. {x1 x 2 , x1 ~ x1 x 3 }

18. {x1 → x 2 ,0, x1 ~ x 2 }

4. {0,1, x1 ( x 2 ~ x 3 ) ∨ x1 ( x1 ⊕ x 3 )}

19. {x1 ⊕ x 2 , x1 }

5. { x , ( 0010), ( 0100111001110001)}

20. {x1 x 2 ∨ x1 x 3 ∨ x 2 x 3 ,0,1}

6. {↔, ¬ }

21. {→, ↔,0}

7. {↓}

22. {x1 x 2 ∨ x1 x 3 ∨ x 2 x 3 , x1 , x1 → x 2 }

8. {↔,∧}

23. {x → y, y,0}

9.{ ⏐ }

24. {∧, →}

10. {∧, ¬ }

25. {→, ↔}

11. {∨, ¬ }

26. {⊕, →}

12. {x1 ↔ x2 , x1 , x1 → x2 }

27. {∧, →}

13. {x1 → x2 , x2 → x1 x3}

28 {⊕, ↔ }

14. {x,(0001), (0010101001010001)}

29.{ ¬ x, (0010), (01011100011)}

15. {x1 → x 2 , x1 }

30. {x1 ↔ x2 , x1 , x1 → x2 }

10.Упростить схемы.

x

y

y

1.

x

y

x

x

z 2. x

z y

y 9

y

x

z

3.

x x

z

y

4.

x

z

y

x

y z

x

z

y

5.

y z y

6.

x

y

x

y

x

z

y

y

z

y

x

y

7. x

z z 8.

x

y

y

z

x

y

x

9.

x

y

x

z

y

z y

x

10. x

y

x

y

10

a c

b

11.

b

a c

12.

a

a

a

b

b

b

c

c

c

b

a

a

13.

c c

b

y

y

x

14.

15.

z

x

z

x

x

y

y

z

z x

y

x

16.

x

z

y

z

z

x

17. x x

y y

z z

y

z 11

x

z y 18.

z y x

z

x

19.

x

y

x

y a

c

b

20. a c

Решение задач 30-го варианта.

1.30. Составим таблицу истинности для формулы B → A :

B

A

B

A

B→A

0

0

1

1

1

0

1

1

0

0

1

0

0

1

1

1

1

0

0

1

2.30. Проверим эквивалентность формул A ∨ B и A ∧ B , составив для них таблицы истинности. A

B

A∨ B

B

A∧ B

A∧ B

12

0

0

0

1

0

1

0

1

1

0

0

1

1

0

1

1

1

0

1

1

1

0

0

1

Формулы не эквивалентны, так как 3-й и 6-й столбцы таблицы не совпадают. 3.30. Для упрощения формулы используем правило исключения импликации: A1 → A2 = A1 ∨ A2 .

¬( A1 → A2 ) ∨ ( A2 → A1 ) = ( A1 ∨ A2 ) ∨ A2 ∨ A1 = ( A1 ∧ A2 ) ∨ A2 ∨ A1 =

= ( A1 ∧ A2 ) ∨ A2 ∨ A1 = A2 ∧ ( A1 ∨ 1) ∨ A1 = A2 ∨ A1 . 4.30. Используя законы логики приведем формулу ( A ∧ B ) ∨ C к виду, содержащему только дизъюнкции элементарных конъюнкций. Полученная формула и будет искомой ДНФ:

( A ∧ B) ∨ C = ( A ∧ B) ∧ C = ( A ∨ B ) ∧ C = ( A ∧ C ) ∨ ( B ∧ C ) Для построения СДНФ составим таблицу истинности для данной формулы:

A

B

C

A∧B

(A∧B)∨C

( A ∧ B) ∨ C

0

0

0

0

0

1

0

0

1

0

1

0

0

1

0

0

0

1

0

1

1

0

1

0

1

0

0

0

0

1

1

0

1

0

1

0

1

1

0

1

1

0

1

1

1

1

1

0

Помечаем те строки таблицы, в которых формула (последний столбец) принимает значение “1”. Для каждой такой строки выпишем формулу, истинную на наборе переменных

A,B,C данной строки: строка 1 – A ∧ B ∧ C ; строка 3 – A ∧ B ∧ C ; строка 5 –

A ∧ B ∧ C . Дизъюнкция этих трех формул будет принимать значение “1” только на набо-

13

рах переменных в строках 1, 3, 5, а следовательно и будет искомой совершенной дизьюнктивной нормальной формой (СДНФ): ( A ∧ B ∧ C ) ∨ ( A ∧ B ∧ C ) ∨ ( A ∧ B ∧ C ) 5.30. Для того, чтобы записать формулу в приведенном виде, следует, пользуясь формулой A → B = A ∨ B , исключить операцию импликации, а затем “опустить” операцию отрицания на простые переменные: A → B ∨ C = A ∨ ( B ∨ C ) = A ∧ B ∨ C = AB C . 6.30. Способ 1. (Метод неопределенных коэффициентов). Составляем таблицу истинности для функции x1 ↔ x2

x1

x2

x1 ↔ x2

0

0

1

0

1

0

1

0

0

1

1

1

Записываем полином Жегалкина с неизвестными коэффициентами a0, a1, a2, a12 для функции от двух переменных: x1 ↔ x2 = a0⊕ a1 x1⊕ a2 x2⊕ a12 x1 x2. Подставляя в это разложение значения x1 и x2 из таблицы, определяем неизвестные коэффициенты: Подставляя x1=0, x2=0, получаем: 1= a0;

x1=0, x2=1 — 0=1⊕ a2 ⇒ a2=1; x1=1, x2=0 — 0=1⊕ a1 ⇒ a1=1; x1=1, x2=1— 1=1⊕ a12 ⇒ a12=0. Полином Жегалкина имеет вид: x1~x2 = 1⊕ x1 ⊕ x2.

Способ 2. (Эквивалентные преобразования). Сначала запишем СДНФ (σ 1 ,σ 2 )

\ /σ f(

1 ,σ 2 ) =1

x1σ 1 x2σ 2 эквивалентности:

x1 ↔ x2 = x1 x2 ∨ x1 x2 = {т.к. x ∨ y = x ⊕ y ⊕ xy } = = x1 x 2 ⊕ x1 x 2 ⊕ x1 x 2 x1 x 2 = {по-

скольку x1 x 2 x1 x 2 = 0 } = x1 x 2 ⊕ x1 x 2 = {далее, x = 1 ⊕ x , поэтому } = (1 ⊕ x1 )(1 ⊕ x2 ) ⊕ x1 x2 = 1 ⊕ x1 ⊕ x 2 ⊕ x1 x 2 ⊕ x1 x 2 = 1 ⊕ x1 ⊕ x 2

7.30. Сначала преобразуем исходную формулу: ( x1 → x 2 ) → x1 x3 = ( x1 ∨ x 2 ) ∨ x1 x3 = x1 x 2 ∨ x1 x3 = x1 ( x 2 ∨ x 3 ) ;

f ( x1 , x 2 , x 3 ) = x1 ( x 2 ∨ x 3 ) . f ( x1 , x2 , x3 ) = x1 ( x2 ∨ x3 ) = x1 ∨ ( x2 ∨ x3 ) = x1 ∨ x2 x3 . Пусть

14

x1 = 0 x 2 = 0 x 3 = 1 , тогда f ( x1 , x 2 , x 3 ) = 0 , f ( x1 , x 2 , x 3 ) = 1 , поэтому f ( x1 , x2 , x3 ) ≠ f ( x1 , x2 , x3 ) , следовательно функция f несамодвойственна.

8.30. Функция f = (1011) немонотонная, т.к. ( 00) < ( 01) , но f (0,0) > f (0,1) . 9.30. Для доказательства полноты системы {x1 ↔ x2 , x1 , x1 → x2 } необходимо проверить, что система содержит функцию не сохраняющую 0, функцию не сохраняющую 1, немонотонную функцию, несамодвойственную функцию и нелинейную функцию. Докажем полноту системы

∑ ={x1 ~ x 2 , x1 , x1 → x 2 } . Обозначим

f 1 ( x1 , x 2 ) = x1 ~ x 2 и выпишем ее

таблицу истинности

x1

x2

x1 ~ x 2

0

0

1

0

1

0

1

0

0

1

1

1

Функция f1 не сохраняет 0. Выясним, является ли f1 самодвойственной.

x1

x2

x1 ~ x 2

f 1 ( x1 , x 2 )

1

1

1

0

1

0

0

1

0

1

0

1

0

0

1

0

Т.к. f 1 ( x1 , x 2 ) ≠ f 1 ( x1 , x 2 ) , то f1 несамодвойственна. Функция f 2 ( x ) = x немонотонная, и не сохраняет 1. Найдем полином Жегалкина для

f 3 ( x1 , x 2 ) = x1 → x 2 = a 0 ⊕ a1 x1 ⊕ a 2 x 2 ⊕ a12 x1 x 2 x1

x2

x1

x2

x1 → x 2

0

0

1

1

1

0

1

1

0

0

1

0

0

1

1

1

1

0

0

1

a 0 = 1 ; 0 = 1 ⊕ a 2 ⇒ a 2 = 1 ; 1 = 1 ⊕ a1 ⇒ a1 = 0 ; 1 = 1 ⊕ 1 ⊕ a12 ⇒ a12 = 1 ;

15

Функция f 3 ( x1 , x 2 ) = x1 → x 2 = 1 ⊕ x 2 ⊕ x1 x 2 нелинейная. Согласно теореме о полноте

∑

– полная система.

10.20. Составим функцию проводимости для схемы:

f (a, b, c) = (a ∨ c) ∨ [(a ∨ b) ∧ c] = (a ∨ c) ∨ [ac ∨ bc] = a ∨ c ∨ ac ∨ bc = a ∨ c. Полученной формуле соответствует схема: a c

Редактор: Литвинова А.А. ЛР № 020639 от 26.04.96. В набор

. В печать

Объём 1,0 усл. п.л. 0,7 уч.-изд. л. Офсет. Формат 60х84/16 Бумага тип № 3. Заказ №

Тираж 200

Цена 5 р.

Издательский центр ДГТУ Адрес университета и полиграфического предприятия: 344010, г. Ростов-на-Дону, пл. Гагарина, 1.

16