Chapter 3 - Boolean Functions Flashcards
see notes on the book for an explanation (found in notes app under #learning)
what is a boolean function
“a function where both arguments and results form a 2 element set” = anything where input and output is binary = a binary system
this does not mean you can only have 2 input variables - this definition applies to each variable separately
give an example of a boolean function
- any acceptable response which takes a binary input variable and outputs a binary value -
example: a pixel drawing system that cuts the edges off a picture - each tile has a function and an input of on or off. Then the function leads to the output of on or off. (own idea)
what is the symbol for AND,
what does AND operator do
a dot in the centre
returns true if both inputs are true
what is the symbol for NOT
’
a) how many boolean functions are there for a 1 variable boolean system
b) and state these possible functions
4 functions
a function maps a variable state (0 or 1) to an outcome (also 0 or 1) - so you can have a function that maps everything to 1, everything to 0, calls false, or calls true for all (maps to identical value)
https://cs.fit.edu/~wds/classes/adm/Lectures/BooleanFunctions.pdf
a) how many boolean functions are there for a 2 variable system?
16 - as each input-output sequence has a unique function
https://cs.fit.edu/~wds/classes/adm/Lectures/BooleanFunctions.pdf
how many boolean functions are there for an n-variable system?
the number of unique input output sequences = the number of functions
so its 2 to the power n for the number of inputs, and then 2 to the power of that for the number of input output sequences
https://cs.fit.edu/~wds/classes/adm/Lectures/BooleanFunctions.pdf
how would you describe the function which creates this truth table:
Function = (X’ANDY’)’AND(XANDY’)’
see. notes for an explanation of this
Prove that ‘ and AND form a minimal complete base for a 2 variable boolean
basic structure:
- prove a function can be described as an AND sentence of every condition upon which the input-output sequence = 0
- prove that the components of this AND sentence can be described with and AND, NOT combination phrase
- prove that AND and NOT dont form a complete base separately by finding a counter example
see. notes on Chapter 3 under the same title as this question #learning
what is the symbol for OR and what does it mean
+
if X or Y is true then function = true
a)what does exclusive OR mean and
b)what is its symbol
c) how do you describe it in terms of AND, NOT and OR
d)how do you describe it just in terms of AND, NOT
a)either X is true then function is true or y is true and then function true but if both are true then function is false - bascially it means its false if X and Y are the same
b)⊕
c) X’ AND Y + X AND Y’ = function (true)
d) function = (XANDY)’ AND (X’ANDY’)’
a) what does the equivalence operator mean
b)what is its symbol
c)give an example of a truth table which has an equivalence function
d)describe the operator in terms of AND, NOT and OR
e) descirbe the operator in terms of AND, NOT
a) that each variable being equal to O or 1 is equivalent in terms of meaning as the outcome is the same whether the variable equals 0 or 1
b)≡
c) the truth table with the usual inputs and the outputs 1, 0, 0, 1 in order top to bottom
d) funtion (true) if XANDY + X’ANDY’
e) function (true) if (X’ANDY)’ AND (Y’ANDX)’
https://cs.fit.edu/~wds/classes/adm/Lectures/BooleanFunctions.pdf
a) that if x is true y should be true (as its implied), but that y could be true without x being true (as its only implied they arent reliant on each other), both could be false, BUT the statement is false if x is true and y is false - as the truth of x is meant to imply the truth of y and when it isnt the implication relationship is rendered false
b) a computer being plugged in and working well (if it is plugged in and not working well something is definitely wrong (false) but in all other scenarios the system works as the computer being plugged in implies it will work well. If its not plugged it, it wont work well. even if its not plugged in it might work if it still has battery.
c) ⟶
d) X’ORY
e) (Y’ANDX)’
a)What is nonimplication
b)what is the symbol for it
c)what is the venn diagram for it
d)what is the expression of it in terms of AND and NOT
a)the opposite of implication - the truth table is reversed - the system only shows nonimplication is true when the implication is contradicted, when X is true and Y is false - in all other states the implication is not contradicted
b)↛
c) picture
d)XANDY’
a) what is reverse implication?
b) what is the symbol for it?
c)express this in terms of AND, NOT
a)the reverse of an x->y implication, hence a y ->x implication
b) ⇐ (or a normal type of arrow←)
c) XANDY’
Express this truth table as a function with operators AND, NOT, OR and then with just AND, NOT and then choose the best way to describe the function out of the two
then state what this function is the opposite of (which function has an inverted truth table)
i think - (X’ANDY’)+(X’ANDY)+(XANDY’)
certain: (XANDY)’
the latter as its faster
the AND function
Further explanation: from what i can tell there are 2 main ways to describe logic gates: expressing all functions which lead to the outcome true and linking them with an OR so that if any are present the function outputs true. Or joining functions which lead to an output of 0 using an AND operator, meaning if any input which (when a particular function acts upon that input) outputs 0, the whole function collapses to 0 due to the nature of the AND operator.
a) what is reverse nonimplication
b)what is the symbol
c)express it in terms of AND and NOT
a) the inversion of the nonimplication of x->y, and hence y does not imply x. This means the only true one is where y =1 and x =0 as that shows the nonimplication of y->x
b) ⇍ (or normal arrow to left with cross through it of course)
c) YANDX’
this is very simple
what is the projection/identity operation
b)what is its symbol
c)how would you express it
a)literally just take whatever x or y is (specified by projection (x or y respectively)) and that is the outcome
b)x or y depending on which is being projected
c)x or y depending on which is being projected
Constant 0 and constant 1 are similar and too obvious for a flashcard - this is just a happy reminder that they exist:)
a)what is the NAND operation
b)give an example of the NAND operation’s use in real life
c) what is the symbol for NAND?
d)express NAND as a combination of AND and NOT
a)it is the negation of the AND function - so it is only false when X and Y are both true
b) if it is both sunny and i have tested positive for a disease where i shouldnt go out in the sun, i shouldnt go outside but in all other cases i could go outside
c)|
d) (XANDY)’
what is the NOR function
b)what is its symbol
c) express it in terms of AND, NOT and OR
d)express it in terms of AND and NOT
a) only true when not X or Y is true
b)↓
c) (X+Y)’
d) (X’ANDY’) i think
explain why AND and NOT operators form a minimal complete base for n variable booleans (not just 2 variable ones)
apply the same method to create the function as before:
1. find rows which = 0, and find a function that expresses that row by taking NOT of any 1 values, and stringing them all together in a big AND function which has value 1 if that string is inputted into the function. Then negate that, as this line = 0 not 1
2. string each of these expressions together using AND
3. tada! sorted :)
prove that
a) OR and NOT forms a minimal complete base for any number of variables
- use the AND, NOT expressions to get an expression for each singular input sequence ON with the rest OFF ( see notes)
- use the substitution of OR and NOT expression of the AND function to make these expressions into OR and NOT expressions
- as the AND tracks outwards to multiple variables no problem, so does the NOT/OR expression of the AND so
- everything is awesome!
see fuller explanation in notes app - TNTO - Chapter 3 - complete minimal base proofs.2
prove that
a)AND, equivalent and exclusive or forms a minimal complete base for any number of variables
proof has same structure as others - however this needs work
see. fuller explanation in notes app - TNTO - Chapter 3 - complete minimal base proofs.3
