All Questions
Tagged with propositional-calculus boolean-algebra
322
questions
0
votes
0
answers
32
views
A generalized algorithm to convert a formula in algebraic normal form to an equivalent formula that minimizes the number of bitwise operations
In this question, “bitwise operation” means any operation from the set {XOR, AND, OR}. The NOT operation is not included because ...
- 922
2
votes
1
answer
35
views
Generate as short as possible boolean formula from a given truth table
Given a truth table, maybe 3-vars, 5-vars or even 10-vars, i can write its formula in DNF or CNF, and simplify it using K-Map or Quine-McCluskey algorithm. But it is based on {NOT, AND, OR}.
Now the ...
0
votes
0
answers
45
views
Can any finite set of binary sequences be expressed as CNF/DNF
I am new to logic and cannot figure out if there are instances when a given set of binary sequences of equal length is not possible to express as a conjunctive or disjunctive normal form. If such sets ...
- 387
2
votes
1
answer
85
views
Why can a compound biconditional statement whose individual statements don't all have the same truth values be true?
Why can $P_1 ⇔ P_2 ⇔ P_3 ⇔ \ldots ⇔ P_n$ be true when not all the $P$’s have the same truth value?
For example: If P1 = T P2 = T P3 = F P4 = F would this be true?
T(P1) ⇔ T(P2) ⇔ F(P3) ⇔ F(P4) =
...
0
votes
2
answers
120
views
Why is the distributive law incorrect here?
I am trying to simplify:
$(p \lor \neg q) \land (p \lor q) $
One thing, I identify from the table is this:
$(p \lor q) \land (p \lor r) $ is second distributive law which becomes $p \lor (q \land r) $
...
- 269
0
votes
1
answer
69
views
I need help with this propositional logic problem
I study compound statements, and I encountered this problem in the book:
The problem
I tried a solution: Let p be proposition "The first door leads to freedom" and let q be proposition "...
0
votes
1
answer
52
views
How to prove two tables are logically equivalent if they have different numbers of variables?
I used boolean algebra to simplify an expression with $3$ variables. After simplifying, it reduces to $2$ variables. The first truth table has $8$ rows and the second one has $4$. How to prove that ...
7
votes
2
answers
253
views
Why is $((p \land q) \Rightarrow z) \Rightarrow (p \Rightarrow z) \lor (q \Rightarrow z)$ true?
I will propose a counterexample to $$((p \land q) \Rightarrow z) \Rightarrow ((p \Rightarrow z) \lor (q \Rightarrow z)).$$ Let's assume that $p$ is "$n$ is divisible by $2$", $q$ is "$n$...
1
vote
2
answers
83
views
Propositional tautologies whose analogues for sets are false
Are there tautologies of propositional logic whose analogues for sets are false? I believe I have found such a tautology. For example, $((p \rightarrow q) \vee (q \rightarrow p))$ is a tautology, but ...
- 21.3k
1
vote
1
answer
28
views
Finding a Proposition to Satisfy Given Logical Statements
I'm facing a logical inference problem and seeking guidance to find a proposition p3 that satisfies certain logical conditions.
Given propositions:
p1 = p or r
p2 = q => !p
p3=?
Given conclusions:
...
- 157
0
votes
0
answers
84
views
Prove $\vdash(A\supset B)\supset C\equiv C\overline{\vee }[A\wedge \neg(B\vee C)]$ using your favorite method
I've been playing with Boolean logic vs ordinary laws of logic like DeMorgan's etc., and I've come up with the following theorem in about 4 lines: $$[(A\supset B)\supset C]\equiv \left\{C\overline{\...
- 1,545
1
vote
4
answers
164
views
Understanding absorption law
I can't understand how absorption law is obtained. I get following steps.
$$a∨(a∧𝑏) = (a∧⊤)∨(a∧𝑏)$$
$$=(a∨a)∧(a∨b)∧(⊤∨a)∧(⊤∨b)$$
then,
I come up with $$=a∧(a∨b)∧⊤∧⊤$$ $$=a∧(a∨b)$$
But, I cannot get $...
-2
votes
2
answers
61
views
How to form a CNF of following formula [closed]
We got an exercise to make a CNF out of the following formula: $$G = ((A \vee \neg B \vee C) \wedge (C \vee D)) \vee ((A \vee \neg C) \wedge (B \wedge D))$$ I've tried to make an equivalent equation ...
2
votes
1
answer
117
views
Satisfiability in an Heyting algebra implies satisfiability in a Boolean algebra for propositional logic?
Let $\mathcal{L}$ be a propositional language and let $\text{Prop}(\mathcal{L})$ be the set of all the propositions of the language $\mathcal{L}$.
Let $(H,\wedge,\vee,\rightarrow,1,0)$ be an Heyting ...
- 455
0
votes
1
answer
56
views
Relation $\vDash$ and inequality of the evaluation functions
Let's consider two propositions $\phi$ and $\psi$ of a propositional language $L$.
Let's suppose that $\phi \vDash \psi$, that is, that for every Boolean algebra $B$ and for every evaluation function $...
- 455