All Questions
Tagged with propositional-calculus boolean-algebra
322
questions
3
votes
5
answers
11k
views
Algebraic proof of De Morgan's Theorems
Could someone give me an algebraic proof of De Morgan's Theorems?
I already know the graphic proof with the truth table, but I need to understand the algebraic way.
EDIT
I try to explain better. ...
- 483
3
votes
4
answers
838
views
How is material implication the same as subset?
I've been told and read a number of times that implies, $\implies$, is the same as subset $\subseteq$. For example, in the wikipedia page on iff it states that "P only if Q", "if P then ...
- 1,324
3
votes
5
answers
425
views
The logic involved in contradiction via the irrationality of $\sqrt{2}$ as an example
I first want to issue my own interpretation of the proof that $\sqrt{2}$ is irrational.
First, for the sake of contradiction, let's assume it is in fact rational. This means we can write $\sqrt{2} = ...
- 5,651
3
votes
2
answers
74
views
Reducing Boolean expression to an equivalent form
Consider two points from an arbitrary subset of $\mathfrak{R}^n$, namely, points $$p_1 = (x_{11}, x_{12}, \dots, x_{1n})$$ and $$p_2 =(x_{21}, x_{22}, \dots, x_{2n})$$
Let $P_1$ denote the ...
- 85
3
votes
1
answer
139
views
Chains in the Lindenbaum algebra
What is the easiest example of an infinite chain in a Lindenbaum algebra for the propositional calculus?
Does there exist an infinite antichain in a Lindenbaum algebra?
- 133
3
votes
3
answers
2k
views
Logic Knights and Knaves problem involving implication question
I'm kinda stuck on the following puzzle problem, and I will appreciate it if anyone can help point out any logic errors.
Question:
John and Sarah are members of the island of knights and knaves, ...
3
votes
2
answers
211
views
Propositional logic: Proof question (p∧q)→r⊢(p→q)→r
Am I correct to assume that there is no proof for $$(p∧q)→r ⊢ (p→q)→r$$
I´ve spent hours trying to figure it out, by now I suspect there might have been a mistake in the exercise. I have been able to ...
- 33
3
votes
1
answer
78
views
Going from (p ∧ ~q) ∨ (~p ∧ q) to (p ∨ q) ∧ (~p ∨~q)
I am confused on how to go from (p ∧ ~q) ∨ (~p ∧ q) to (p ∨ q) ∧ (~p ∨ ~q). I know they are equal because I plugged them into a truth table and all of the rows have the same values. What would be some ...
3
votes
1
answer
470
views
Boolean Algebra Transform
I am revisiting Boolean algebra after a long while.
Can somebody help show me how to simplify the LHS to get the RHS?
$$abc * a'bc + (abc)' * (a'bc)'\quad = \quad \;b'+c'$$
- 273
3
votes
1
answer
90
views
proof that any boolean function can be written in canonical form
It's bugging me for a while but although I can vaguely see that when writing canonical forms we kind "build them" in a way specificly to make it be true but I can't grasp exactly why it is ...
- 35
3
votes
2
answers
109
views
Simplifying the boolean expression $AB+BC'D'+AC+AD$
I'd like to simplify the expression
$$AB+BC'D'+AC+AD$$
Logically, I understand why the AB term isn't needed, if both A and B are true, then at least one of the other terms will always be true, making ...
- 33
3
votes
1
answer
126
views
Are parentheses/connectives always necessary in representing expressions built with a single sole sufficient operator?
The Wikipedia page on the Sheffer stroke provides two ways of simplifying expressions consisting only of the Sheffer stroke:
Removing all occurrences of the logical connective '$\mid$' in the ...
- 727
3
votes
2
answers
1k
views
Tautology, Valid, Contingent, Unsatisfiable, Contradiction: relationship?
I am trying to clear my doubts about various terms: tautology, contradiction, contingent, satisifiable, unsatisfiable, valid and invalid. I have read on them from various sources and was thinking ...
- 1,317
3
votes
2
answers
390
views
Proving a boolean algebra relation
I just started reading the book Probability Theory the Logic of Science by Jaynes and on pg. 13 he includes this exercise, which I'm having trouble proving:
$C\equiv(A+\bar B)(\bar A+A \bar B)+\bar ...
- 690
3
votes
1
answer
2k
views
Proving that a set with a ternary logical connective is functionally incomplete (i.e. inadequate)
I am stucked at trying to prove that the set $\{\lnot ,G\}$ of logical connectives is inadequate where $G$ is a ternary connective that gives $T$ (True) if most of its arguments are $T$.
For example: ...
- 2,517