minevi.ru
страница 1
скачать файл
Контрольная работа № 3
Тема работы – математическая логика. В работе требуется выполнить следующие задания.

  1. Определить, является ли справедливой приведенная формула алгебры высказываний, не прибегая к составлению таблицы истинности, а используя только свойства соответствующих операций.

  2. Для указанной функции трех переменных:

  • составить таблицу истинности;

  • определить, к каким классам булевых функций она относится;

  • записать совершенные ДНФ и КНФ;

  • найти минимальную ДНФ;

  • для полученной минимальной ДНФ построить логическую схему в базисах: а) { ٧, } (дизъюнкция, отрицание); б) { ٨, } (конъюнкция, отрицание).

  1. Доказать полноту (или неполноту) приведенной системы булевых функций.

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

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

В качестве примера рассмотрим функции двух переменных f10 = х1  х2 – эквивалентность и f14 = х1 х2 – импликация. Таблица истинности для этих функций имеет вид:

x1

x2

f10

f14

0

0

1

1

0

1

0

1

1

0

0

0

1

1

1

1

Представим f10 в виде полинома по модулю два:

f10(x1, x2) = a0  a1 x1  a2 x2.

Подставляя значения функции и переменных из набора № 0, получим

1 = a0  a10  a20, откуда a0 = 1.

Используя аналогичным образом набор № 1, получим (с учетом того, что a0 = 1)

0 = 1  a10  a21, откуда a2 = 1.

Из набора № 2:

0 = 1  a11  a20, откуда a1 = 1.

Подставляя полученные значения коэффициентов в выражение, где значения переменных и функции соответствуют набору № 3, получим

1 = 1  1  1, что является истиной. Отсюда следует, что функция х1  х2 линейна и может быть представлена как

х1  х2 = 1  х1  х2.

Исследуя аналогичным образом функцию f14 = х1 х2, получим:

a0 = 1 (из набора № 0);

a2 = 0 (из набора № 1);

a1 = 1 (из набора № 2).

Используя для проверки набор № 3, получим

1 = 1  1  0, что является ложью. Следовательно, функция f14 = х1 х2 нелинейна.


Вариант 6

  1. Верно ли, что

А ٨ В ٨ С ٨ (D ٧E ) = А ٧B ٧C ٧ D ٨ E,

где А, В, С, D, E – простые высказывания?


  1. Функция f(x1, x2, x3) принимает единичные значения на наборах №№ 1, 2, 3, 5, 7.

  2. Является ли полной система булевых функций, состоящая из импликации и эквивалентности?

Контрольная работа № 4


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

  1. Приведите три самостоятельных примера применения оператора подстановки к простейшим числовым функциям. Например,

s(С23 (I13 (3, 2, 4), I23 (5, 8, 1), I33( 5, 6, 7))) = 3.

  1. Приведите два самостоятельных примера применения оператора примитивной рекурсии (аналогично примерам из конспекта лекций).

  2. Напишите программу для машины Тьюринга в соответствии с Вашим вариантом.

  3. Решите комбинаторную задачу в соответствии с Вашим вариантом.


Вариант 6

  1. Составьте программу машины Тьюринга, печатающей число 1. В результате работы программы происходит следующее преобразование машинных слов:

01x q11y 0000  0 1x +y 0 1q010.

  1. Сколькими способами можно выбрать 6 карт из колоды, содержащей 52 карты так, чтобы среди них были карты каждой масти?
скачать файл



Смотрите также:
Математическая логика. В работе требуется выполнить следующие задания
31,42kb.
Памятка «Как выполнять домашние задания»
20,84kb.
Как работать с Порталом арм дубп
64,19kb.
Задания к семинарским занятиям 2 семестр тема конституционное законодательство стюартов проблемные задания, таблицы, эссе Вид задания
31,63kb.
«Улицы Красноярска». Конкурс посвящён выдающимся людям и землякам-красноярцам, жившим и работавшим в Красноярском крае, именами которых названы улицы города
46,89kb.
Логика. Теория аргументации
266,72kb.
Оргкомитет конференции председатель оргкомитета
45,77kb.
Контрольная работа по дисциплине «Логика» Для студентов заочной формы обучения
35,78kb.
Должностная инструкция менеджера–администратора по работе с юридическими лицами отдела по работе с vip-клиентами
49,2kb.
номенклатура продукции и мощность производства по основным видам ее (в натуральном и стоимостном выражении) на полное развитие и на первую очередь
87,76kb.
Письмо без ошибок советы родителям
8,47kb.
Из опыта работы учителя английского языка Шахницкой Л. А
71,15kb.