All Questions
5
questions
3
votes
2
answers
114
views
Proof by induction of inadequacy of a propositional connective
I have the following truth table of a newly defined logical operator and have to prove its functional incompleteness via structural induction.
My idea is that that you cannot express the always true ...
-1
votes
1
answer
206
views
Logic in Computer Science - Define inclusive XOR by induction [closed]
What is the formal definition by induction for iterated exclusive or (XOR) from $i = 1$ to $n$. Thanks
This is the notation: $\bigoplus_{i=1}^n A_i$.
4
votes
1
answer
2k
views
Proof of Principle of Duality: Show that $φ$' is logically equivalent to $¬φ$
Could anyone check if my proof is ok/ suggest any improvement please? I couldn't find a way to utilise the induction hypothesis so I am not sure if this is ok.
Let $φ$ be a formula built up using ...
0
votes
1
answer
981
views
Changing conjunction and disjunction in equivalent boolean functions.
I have some difficulties to prove that if two equivalent boolean functions contain only ∧, ∨ and $\neg$ than we can change ∧ to ∨ and vice versa and the result functions will remain equivalent.
There'...
1
vote
1
answer
1k
views
Using induction to prove universality of gate
Can we use induction to prove gate(like NAND) is universal. If so how?