Основные понятия и определения. Будем рассматривать только функции конечного числа аргументов

Будем рассматривать только функции конечного числа аргументов.

Рассмотрим множество векторов ={<x₁, …, x_n>}, координаты которых могут принимать лишь два значения - 0 или 1. Тогда множество состоит из 2ⁿ различных векторов. Сопоставим каждому вектору из символы 0 или 1, т.е. произведем однозначное отображение множества X на множество Y = {0,1}.

Определение 1.1.1. Функцией алгебры логики, или переключательной функцией, называется функция, дающая однозначное отображение в Y [1].

Из этого определения следует, что функция f(x_{1, …,}x_n) называется переключательной, если она, так же как и ее аргументы, может принимать только значения из двухбуквенного алфавита, например, 0 и 1.

Поскольку аргументы переключательной функции могут принимать только два значения, то область определения любой переключательной функции конечна. Совокупность значений аргументов называется набором и обозначается a₁, …, a_i, …, a_n, где a_i равно 0 или 1 (i = 1, …, n). Каждый набор может быть представлен n–разрядным двоичным числом, а количество двоичных n–разрядных чисел равно 2ⁿ. Поэтому любая переключательная функция может быть определена на 2ⁿ наборах.

Например, переключательные функции двух аргументов определены на четырех наборах (00, 01, 10, 11), а переключательные функции трех аргументов – на восьми. Таким образом, переключательная функция может быть задана таблицей, в которой перечислены все возможные значения аргументов функции (наборы) и соответствующие этим наборам значения функции. Такая таблица называется таблицей истинности переключательной функции. Пример переключательной функции трех аргументов приведен в табл. 1.1.

Таблица 1.1

Таблица значений переключательной функции

x1
x2
x3
f(x1,x2,x3)

Каждому набору аргументов можно приписать номер, равный двоичному числу, соответствующему данному набору:

0,0,0,0,0 — нулевой набор;

0,0,0,0,1 — первый набор;

.......................

1,1,1,1,1 — тридцать первый набор.

Набор, содержащий все единицы (1,1, …, 1), называют единичным набором.

Переключательная функция n аргументов определена на 2ⁿ наборах, на которых она может принимать значения 0 или 1. Поэтому в соответствие каждой переключательной функции можно поставить 2ⁿ-разрядное двоичное число. Количество 2ⁿ-разрядных двоичных чисел равно . Таким образом, число различных переключательных функций n аргументов конечно и равно .

Припишем каждой переключательной функции номер, равный двоичному числу, образованному значениями переключательной функции на всех наборах. Этот номер записывается слева направо, начиная со значения функции на нулевом наборе. Например, двоичное число, образованное значениями функции из табл. 1.1, 00111010₍₂₎, равно 58 в десятичной системе счисления и функцию можно обозначить следующим образом:

f(x₁,x₂,x₃) = f₅₈(x₁,x₂,x₃).

Пример 1.1. Составить таблицу истинности для переключательной функции номер 23805 четырех аргументов.

Решение. Переключательная функция четырех аргументов определяется на 2⁴ = 16 наборах (табл. 1.2). Для получения значений функций представим число 23805 в двоичной системе счисления: 23805₍₁₀₎ =

= 101110011111101₍₂₎. Полученное двоичное число имеет 15 двоичных разрядов, и для представления переключательной функции необходимо дополнить полученный код до 16-разрядного: 0101110011111101.

Таблица 1.2

Таблица переключательной функции f₂₃₈₀₅(x₁,x₂,x₃,x₄)

x1

x2

x3

x4

f23805(x1,x2,x3,x4)

Определение 1.1.2. Если две переключательные функции f(x₁, …, x_n) и φ(x₁, …, x_n) одного и того же числа аргументов принимают на всех возможных наборах значений аргументов одинаковые значения, то функции f и φ называются равными.

Факт равенства функций f и φ записывается так:

f(x₁, …, x_n) = φ(x₁, …, x_n).

Определение 1.1.3. Переключательная функция f(x₁, …x_i-1,x_i,x_i+1, …, x_n) существенно зависит от аргумента x_i, если имеет место соотношение

f(x₁, …x_i-1, 0, x_i+1, …, x_n) ¹f(x₁, …x_i-1, 1, x_i+1, …, x_n).

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

Дата добавления: 2014-01-06