# Questions tagged [propositional-calculus]

Appropriate for questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions. Also for general questions about the propositional calculus itself, including its semantics and proof theory. Questions about other kinds of logic should use a different tag, such as (logic), (predicate-logic), or (first-order-logic).

3,562 questions
43 views

32 views

### Mathematical Logic Inference theory

Show that $(L \lor m)$ logically follows from: $p\land q\land r$ $(q\leftrightarrow r) \to (L \lor m)$ how to solve this using inference theory? i could get till here, p,q,r --- (rule p) (q → r) ∧ (...
37 views

### How to represent variables that are “mutually different” in proposition logic?

For example, how can I rewrite $$\forall a\exists b\exists c\exists d\forall e\left({a\ne b\wedge a\ne c\wedge a\ne d\wedge b\ne c\wedge b\ne d\wedge c\ne d\wedge P\left({e,a}\right)}\right)$$ into a ...
39 views

### Why is this “proof” actually not a proof of SL's soundness?

Here, I'll consider only sentential logic as : sentential language and semantics + natural deduction rules. Alledged "proof" : (1) each rule of natural deduction is guaranteed or justified by a ...
33 views

### What is the relativisation of a formula by a formula?

I wrote an Email to my Logic professor, asking him what the relativisation of a formula wrt. a formula was. Unfortunately, he said he wouldn't tell by mail. Thus, I have to turn to the internet ...
54 views

### What is the contrary - not the contradictory - of $(A\rightarrow B)$?

In traditional logic, there was a distinction between " contradictory" sentences and " contrary" sentences. The relation holding between contrary sentences meant maximal opposition. For example, the ...
60 views

### Simplification of the boolean expression

Simplify the following expressions to the simplest expression using De Morgan's theorem and Boolean algebra. AB+(C+B')(AB+C') =AB+ABC+CC'+ABB'+B'C' =AB+CC'+A+B'C' =A+CC'+B'C' =A+B'C'
70 views

### Can natural deduction prove it's own rules, as my logic book says? Is there a level confusion there?

I'm currently studying John Nolt's Outline of Logic ( Schaum's series). According to the author, one can use natural deduction to prove some rules of natural deduction itself, for example the ...
146 views

### Does “$\lnot P$” mean “$P$ is false”? Or not? ( syntax versus semantics)

[ edited 11th april 2019] Does the distinction between syntax and semantics imply that ( rigorously) the negation of P should not be read as " P is false"? I'll try by the following comments to ...
48 views

### Union of sets and set satisfiability and tautologies

I was troubled with these two questions: I have to prove/refute many statements, but only two of which troubled me: (1) If $A ∪ B$ is satisfiable, then both $A$ and $B$ are satisfiable. I know for a ...
38 views

### Need help to simplify- logic algebra

{( ∼p ∨ ∼q ∨ r) ∧ (p ∧ r)} ∨ {p ∧ (∼q ∨ r)} I started like that and then i have no idea what to do....can anyone give a hint please. {( ∼p ∨ ∼q ∨ r) ∧ (p ∧ r)} ∨ (p ∧ ∼q) ∨ (p ∧ r) Book answer ...
26 views

### Is it possible to represent “A implies B” , “ A iff B” , “ A Xor B ” using a switching circuit diagram?

One commonly sees conjonction represented by 2 swiches on the same line ( " en série" as one says in French) and inclusive disjunction by 2 switches in parallel. But I've never seen the circuit that ...
57 views

13 views

### Implement 4-variable boolean functions using a 2x4 decoder and a 2-bit magnitude comparator

As mentioned, I am given a 2x4 decoder and a 2-bit magnitude comparator. I am to implement the following 4-variable Boolean functions using either or both. The use of any other logic gates is ...
25 views

### Simplify a 15-variable Boolean function in minterms and maxterms

What is the approach to simplify this expression? Supposedly this should be done fairly easily without the use of calculators. (m = minterms, M = maxterms) (m315 * M987 * m1025) + m895 * (M222 + M618)...
23 views

### Boolean logic simplification of $a * b' * c' * d' + a * b + b * d' + b * c * d$

The expression $a * b' * c' * d' + a * b + b * d' + b * c * d$ becomes $a * b + a * c' * d' + b * c + b * d'$, but how can I show that? I can find any laws to solve this. Thanks in advance.
64 views

### Determine the truth value of: $((p \to \neg q)\space\land (\neg r \lor q) \land r) \to \neg p$ without truth table

Determine the truth value of: $$((p \to \neg q)\space\land (\neg r \lor q) \land r) \to \neg p$$ I can determinate it easily with truth tables (it's a tautology), but i want to do it without the ...
34 views

### Prove tautology using propositional equivalence and the laws of logic determine

q ∧ ( p → ¬q) → ¬p q ∧ ( ¬p ∨ ¬q) → ¬p (q ∧ ¬p)∨ (q ∧ ¬q) → ¬p (q ∧ ¬p)∨ F → ¬p i dont know how to solve this further. Kind of leaves me confused what would be ...
27 views

49 views

### Is similar triangles have equal areas a proposition?

Suppose it is a proposition. So we have The conversion proposition is if two triangles have equal areas, then there are similar. The inversion proposition is that if two triangles are not similar, ...
53 views

In the Stanford Encyclopedia's page on Russell's Paradox, we get the following anecdote about an additional, lesser-known paradox from Russell: ...in Appendix B Russell also presents another ...
24 views

### Need help proving this entailment where the KB has sentences with multiple conjuncts

Show formally (using a proof rather than a Truth Table) that A follows from the given sentences shown. P ∧ Z (¬R ∧ ¬W) ∨ (¬P) (W ∧ Q) ⇒ P Q ∨ W Q ⇒ (A ∨ P) ...
### Show that $\vdash \Gamma \cup \{\psi\}$ implies $\vdash \Gamma \cup \{\psi'\}$ where $\psi'$ is $\psi$ with one of its bound variables renamed.
My textbook says that it is clear that: $\vdash \Gamma \cup \{\psi\}$ implies $\vdash \Gamma \cup \psi'$, where $\psi'$ is just $\psi$ with one of its bound variables renamed. I am trying to show ...