All Questions
Tagged with propositional-calculus boolean-algebra
322
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 ...
- 51
3
votes
2
answers
1k
views
Simplify $(P \wedge Q \wedge R)\vee(\neg P\wedge Q\wedge\neg R)\vee(\neg P\wedge\neg Q\wedge R)\vee(\neg P \wedge\neg Q\wedge\neg R)$
Let $\psi_{1} := (P \wedge Q \wedge R)\vee(\neg P\wedge Q\wedge\neg R)\vee(\neg P\wedge\neg Q\wedge R)\vee(\neg P \wedge\neg Q\wedge\neg R)$ and
Let $\psi_{2} := (\neg P \wedge \neg Q) \vee (\neg P \...
3
votes
1
answer
117
views
Prove if Tautology, Contradicton, or Neither. Is my proof ok?
Determine whether $((p \Rightarrow q) \Rightarrow r) \Leftrightarrow (p \Rightarrow (q \Rightarrow r))$ is a tautology, a contradiction, or neither.
If $p,q,r
= (0,0,0)$
then $((p \Rightarrow q)\...
- 75
3
votes
0
answers
103
views
Do the integers 1 and 0 mean different things in Boole's original logic and modern Boolean algebra?
I understand that the modern notion of Boolean algebra was adapted by Peirce, Schroder and others from Boole's logic of classes. Boole spoke of 1 and 0 as representing the Universe of Discourse and ...
- 79
2
votes
2
answers
227
views
Can $A+\bar{A}\bar{B}+BC$ get any simpler?
I've simplified this Boolean formula quite a bit. Can it get any simpler? My definition of simple in this case is using the least amount of operators (and, or)
Title is "A or (negative A and negative ...
- 317
2
votes
2
answers
397
views
How to prove that $(A \lor B) \land (\lnot A \lor B) = B$
I know this is fairly basic, and I understand that it becomes
$$
\begin{align}
(A \land \lnot A) \lor B \\
F \lor B \\
B
\end{align}
$$
However, I can't work out how to prove that it becomes that ...
- 269
2
votes
2
answers
10k
views
Simplify [p∧ (¬(¬p v q)) ] v (p ∧ q) so that it become p, q, ¬p, or ¬q
Had a question on a test that asked for us to simplify (using rules of inference) the following proposition: [p∧ (¬(¬p v q)) ] v (p ∧ q)
to p, q, or their negation (¬p, ¬q). Here is what I did:
1) [p∧...
- 123
2
votes
2
answers
5k
views
How to apply De Morgan's law?
If for De Morgan's Laws
$$( xy'+yz')' = (x'+y)(y'+z)$$
Then what if I add more terms to the expression ...
$$(ab'+ac+a'c')' = (a'+b)(a'+c')(a+c)?$$
- 215
2
votes
3
answers
422
views
$((p\to q) \land (q \to p)) \to (p \leftrightarrow q)$ is tautology
$((p\to q) \land (q \to p)) \to (p \leftrightarrow q)$ is tautology
I prove this by using proof by contradiction:
So I defined A = [(p $\implies$ q) $\land$ (q $\implies$ p)] and B = (p $\iff$ q) , ...
- 1,255
2
votes
4
answers
12k
views
Show that (P→Q) ∧ (Q→R) is equivalent to (P→R) ∧ [(P↔Q) ∨ (R↔Q)]
I literally have no idea how to start this proof.
I get to (P→Q) ∧ (Q→R) = (¬P ∨ Q) ∧ (¬Q ∨ R) and then I get stuck.
- 35
2
votes
2
answers
214
views
Ist it a tautology w/o truth table
AB + CD = (A+C)(A+D)(B+C)(B+D) is a tautology (checked with wolfram alpha)
I have to prove this whith boolean algebra but I don't get it right.
That'S what I have:
AB + CD = A(C+D)B(C+D)
AB + CD = ...
- 35
2
votes
4
answers
91
views
Where does this rule for Boolean simplification come from?
In the simplification:
$$\begin{align}A'BC + AB'C + ABC \\
BC(A' + A) + AB'C \\
BC + AB'C \\
\color{red}{C(B + AB')} \\
\color{blue}{C(B + A)} \\
AC + BC\end{align}$$
What is the rule that permits ...
- 5,651
2
votes
3
answers
1k
views
Solving this logical puzzle by resolution doesn't work for me
In this document there is a logical puzzle:
If the unicorn is mythical, then it is immortal. If the unicorn is not mythical, then it is a mortal mammal. If the unicorn is either immortal or a ...
- 1,495
2
votes
1
answer
780
views
What is the relationship between propositional calculus, set theory, and Boolean algebra?
The connective $∧$ (conjunction) in propositional logic is essentially the same as ∩ (intersection) in set theory if one thinks of 'false' as 'not a member' and 'true' as 'a member'. De Morgan's laws, ...
2
votes
3
answers
531
views
Construct XNOR with only OR gates
Is it possible to construct the XNOR gate which is given as, a XNOR b = (a AND b) OR (~a AND ~b), by using only OR gates. So from the definition, the question boils down to: can you construct the AND ...
- 21