in Mathematical Logic edited by
423 views
5 votes
5 votes

A function $f:\{0,1\}^n \rightarrow \{0,1\}$ is called an $\textit{n-ary Boolean function}$ or  $\textit{truth function}.$   
      
We denote their totality by the set $\mathbf{B_n}.$     
          
Now, $f \in \mathbf{B_n}$ is called $\textit{linear}$ if $f(x_1,x_2,...,x_n) = a_0 + a_1x_1 + ... + a_nx_n$ for suitable coefficients $a_0,a_1,...,a_n \in \{0,1\}.$ Here $+$ denotes the exclusive disjuction (addition modulo 2) and multiplication is conjunction i.e. $a_ix_i = x_i$ for $a_i=1$ and $a_ix_i = 0$ for $a_i=0.$      
       
The number of $\textit{n-ary linear Boolean functions}$ is:     
       

  1. $2^{2^n}$      
          
  2. $2^{2^{n+1}}$      
            
  3. $2^n$      
           
  4. $2^{n+1}$
in Mathematical Logic edited by
423 views

1 Answer

0 votes
0 votes

$f(x_{1},x_{2},...,x_{n}) = a_{0}+a_{1}x_{1}+...+a_{n}x_{n}$ such that $\forall _{i=0,1,2,..,n}$ $a_{i}, x_{i} $ $\epsilon$ {$0,1$}

In simple words $a_{i}, x_{i} $ take boolean values.

Function $f$ take n boolean variables as input and gives a boolean value as output as per the eqaution.

For better understanding lets go from small

$n=1$

$x_{1}$ $f(x_{1}) = a_{0}+a_{1}x_{1}$ $f_{1}$
$(a_{0}=0,a_{1}=0 )$
$f_{2}$
$(a_{0}=0,a_{1}=1 )$
$f_{3}$
$(a_{0}=1,a_{1}=0 )$
$f_{4}$
$(a_{0}=1,a_{1}=1 )$
0 $a_{0}$ 0 0 1 1
1 $a_{0}+a_{1}$ 0+0 = 0 0+1=1 1+0=1 1+1=0

 

Notice in the truth table that for $x_{1} = 1$, $f(x_{1}) = a_{0}+a_{1}$

we get 4 functions because $a_{0},a_{1}$ takes boolean value.($a_{0},a_{1}$ each can 2 boolean values and hence by product rule total count of number functions $a_{0}$ XOR $a_{1}$ is $2^{2}$).

 We get $2^{(1+1)}$ linear boolean functions when $n=1$

$a_{0}+a_{1}$ also covers all possibilities of functions possible from values of $a_{0}$

Extending this to n variables $(x_{1},x_{2},...,x_{n})$ will get $2^{n}$ rows in truth table in which for values of $(x_{1}=1,x_{2}=1,...,x_{n}=1)$ at last row results in $f(x_{1},x_{2},...,x_{n}) = a_{0}+a_{1}+...+a_{n}$.

There will be $n+1$ $a_{i}$ terms in the last row of the truth table and hence number of possible boolean functions is $2^{(n+1)}$

(Notice that question indirectly asked for number of $n+1$-ary boolean functions possible)

edited by
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true