All Questions
Tagged with propositional-calculus boolean-algebra
322
questions
6
votes
1
answer
193
views
Given the $P⇒Q$ and $¬P$, prove that we cannot deduce $¬Q.$
Given the known theorems $P \Rightarrow Q$ and $\lnot P$, prove that we cannot deduce $\lnot Q.$
I made the truth table for $P \Rightarrow Q:$
Now, if $P \Rightarrow Q$ is a theorem, that means that ...
- 224
6
votes
1
answer
346
views
Construct an OR gate when missing input information
Is there a way to construct an OR gate when the input for one combination is unknown?
For example, suppose that the gate, $X$, outputs for the following inputs, $x_1$ and $x_2$, $x_1 = T$, $x_2 = T$:...
- 391
5
votes
3
answers
431
views
Proving the equivalence without making use of Truth Tables
How would I prove this without using the truth table? If anyone can help me with this it would be greatly appreciated
$$(¬A \lor B) \lor (¬B \lor ¬A) ≡ ¬A$$
This is what I got so far and I'm stuck ...
- 91
4
votes
3
answers
36k
views
How to prove that $[(p \to q) \land (q \to r)] \to (p \to r)$ is a tautology without using the truth table?
I am looking for a way to prove that the statement, $[(p \to q) \land (q \to r)] \to (p \to r)$, is a tautology without the help of the truth table. By using only Laws and Theorems like De Morgan's ...
4
votes
5
answers
430
views
How is $((X\to Y)\to X)\to X$ a tautology?
$((X \rightarrow Y ) \rightarrow X) \rightarrow X$ converted to its disjunctive normal form is $X' + X$.
Why/how does this show me why this formula a tautology?
- 181
4
votes
2
answers
11k
views
is bitwise xor completely associative?
The bitwise xor (exclusive or) operator has the following truth table:
$$
\begin{array}{c|cc}
\text{^}&0&1\\
\hline
0&0&1\\
1&1&0
\end{array}
$$
It is true that if $a,b,c,d$ ...
- 21.9k
4
votes
1
answer
2k
views
Finding the atoms and elements of a Lindenbaum–Tarski algebra
Let B be the Lindenbaum–Tarski algebra with three variables $p,q,r$
(1) Find all the atoms of $B$.
(2) How many elements of does $B$ have?
So I think I know what an atom is, but I'm still not sure ...
- 575
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 ...
- 1,458
4
votes
3
answers
265
views
Why do I keep running into contradictions in this problem (Knights and Knaves variation)?
Edit: I've attempted to solve this another way and posted it as a possible answer. Hesitant to accept it, and would appreciate if anyone could go over it and confirm it's the way to go.
There is an ...
- 329
4
votes
2
answers
277
views
How math deals with state or "algebra of sequential logic"
Boolean algebra is well-studied and you could easily find a lot of introductory materials on different operators, properties, how eveything is nicely related to the algebra of sets, and so on.
Coming ...
- 167
4
votes
1
answer
5k
views
Tseytin transformation example
I am trying to understand Tseytin transformation and I can't really find any reliable info on the internet.
I pretty much understand the steps until I get to the point I have to convert all ...
- 43
4
votes
1
answer
496
views
Can we convert this statement about sets into a statement of propositional logic?
A question was just asked here about proving
$$A⊆(B∪C)⟺A\setminus C⊆B.$$
We can prove this statement directly, using the concepts of first-order logic.
"Suppose $x \in A \setminus C$ and that $A⊆(...
- 68.1k
4
votes
1
answer
4k
views
Lindenbaum Algebras
After reading this page, I still have some questions about Lindenbaum algebras. Assume that the scope is a propositional language with a denumerable set X of propositonal variables.
In that case, the ...
- 41
4
votes
1
answer
293
views
Proving ◦ is either nand or nor if ◦ is a binary operator that can define negation and all other binary operators by itself.
I have a outline of the proof in my book but I am not able to understand the second part of it.
Suppose that $\circ$ is a binary operator that can define all the other operators. Negation
must be ...
- 426
4
votes
3
answers
1k
views
Relation between propositional logic, boolean algebras and truth tables
I am a bit confused with the relation between propositional logic, boolean algebras and truth tables.
Propositional logic starts with a language over a set of primitive propositions, they are called ...
- 41