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).

0
votes
1answer
43 views

$w\models\phi$ or $w\models\neg \phi$

Let $\phi$ be a modal sentence. Let $M$ be a model and $w$ be a world. Is it true that either $w\models\phi$ or $w\models\neg \phi$? I feel it's wrong, but what's wrong about this argument? If $w\...
0
votes
0answers
27 views

Proving validity of this argument

p→ (q→r) q→ (p→r) ∴(p∨q) →r how do i prove the validity of this argument by using the rules of inference? please help i'm stuck there is too much possibility that i'm at a lost on how to start...
1
vote
3answers
84 views

can we a prove ⊢ (α → α) → (α → α)

The system L0 is defined as follows: Axioms: A1 (α → (β → α)) A2 2. (α → (β → γ) → ((α → β) → (α → γ)) A3 ((¬β → ¬α) → ((¬β → α) → β)) In one of my problem sheets, I am told that I am allowed to ...
2
votes
1answer
48 views

Does (∀x(r → p)) ∧ (∀x(p → q)) imply ∀x(r → q)?

So the frustrating thing is that I am asked to decide whether the first implies the second, but I was given no deduction rules for predicate logic except the fact that $ ∀x(r(x) → p(x)) $ implies $ ∀x(...
0
votes
1answer
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) ∧ (...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
2
votes
2answers
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'
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
57 views

Can you simplify $(\cdots ((\alpha_1 \to \alpha_2 )\to \alpha_3 )\cdots \to \alpha_n)$?

I know that the following is true for all formula $\alpha_1, \alpha_2, \cdots, \alpha_n$, $$\vdash (\alpha_1\to(\alpha_2\to(\cdots(\alpha_{n-1}\to\alpha_{n})\cdots))) \leftrightarrow ((\alpha_1\...
2
votes
1answer
77 views

Understanding $\lor~E$ in Natural Deduction?

I'm reading Frank Pfenning's Lecture Notes on Natural Deduction. It's reasonable that the following $\lor$-elimination rule is incorrect since we can have any theorem $\alpha$ given a single theorem $\...
0
votes
2answers
42 views

Can You help me simplify ~Q ∧ (P→Q) ∧ (R ∨ ~Q)?

can you help me solving this problem, I got stucked answering it in the beginning and hoping that you can help me with this. Thanks! ~Q ∧ (P→Q) ∧ (R ∨ ~Q)
0
votes
1answer
61 views

Finding a derivation of $\vdash{(\lnot\lnot{p}\to{p})}$ [duplicate]

I'm reading through Derek Goldrei's "Propositional and Predicate Calculus" book and I've come across an exercise problem that states to show the derivation of "$\vdash{(\lnot\lnot{p}\to{p})}$" using ...
0
votes
1answer
71 views

Why do other logical symbols except $\to$ and $\leftrightarrow$ not have corresponding meta symbols?

The symbols $\to$ and $\leftrightarrow$ have corresponding meta symbols $\Rightarrow$ and $\iff$. But why other symbols like $\wedge, \vee,(,), \cdots $ do not have corresponding meta symbols? Is ...
0
votes
1answer
15 views

Deducing truth values from result of a Boolean operation

I have been given that the following Boolean operation results in "True" and I have been asked to either provide the truth values of $A, B, C$ or explain why it cannot be deduced. $$\left(A \...
0
votes
0answers
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 ...
0
votes
0answers
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)...
1
vote
1answer
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.
1
vote
4answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
27 views

OR equality constraint for binary integer program

I am trying to find a way to implement an OR equality constraint in a Binary Integer Program. For example, say I want to add the following logical condition to the program: $$x_1+x_2+x_3+x_4+x_5 = 1\...
3
votes
0answers
37 views

Proof of Completeness Theorem in Enderton's Logic, satisfiability of $\Gamma \cup \Theta \cup \Lambda$

I'm reading the proof of the Completeness Theorem from Enderton's "A Mathematical Introduction to Logic". I'm having issues seeing how the following highlighted sentence actually holds (excerpt from ...
2
votes
0answers
44 views

Arguments by case

I am taking real analysis, but that is really not important.....the important part is that my professor says that one of my methods of proof is invalid. Essentially he is asking me to prove something ...
1
vote
3answers
61 views

Reconciling Different Definitions of Language

Definition 1 (Formal Language). A language $L$ over an alphabet $\Sigma$ (any nonempty finite set) is a subset of the set of all finite sequences of elements of $\Sigma$, i.e. $L\subseteq\bigcup_{n=0}^...
1
vote
1answer
24 views

How to prove that these propositions show that $f$ is injective?

Let $f$ be a total function on some nonempty set $D$. In the following propositions, x and y are variables ranging over $D$, and g is a variable ranging over total functions on $D$. Indicate all of ...
2
votes
1answer
65 views

How to deduce $\square p\to p$ from other modal axioms?

I'm trying to deduce the T axiom $\square p\to p$ from the B,D,5 (and also K) axioms. B: $q\to\square\diamond q$ D: $\square q\to\diamond q$ 5: $\diamond q\to \square \diamond q$ I tried to assume ...
0
votes
1answer
33 views

How to name a large number of variables in predicate logic?

What is the most common way of naming a large number of variables in predicate logic? I run out of variables pretty easy in long predicate logic sentences. The simple fact of using a lot of letters ...
0
votes
1answer
40 views

Consistency of a sentence in $S5$

True or false: if a modal sentence $\phi$ is consistent in K, then it is consistent in S5. This is equivalent to the contrapositive: if $\phi$ is not consistent in S5, then it's not consistent in K. ...
0
votes
1answer
51 views

Verify the following equivalence by writing an equivalence proof [closed]

How do I show that: $$(p\rightarrow q)\land(p\lor q) \equiv q$$
0
votes
0answers
42 views

$\phi$ satisfiable implies $\square \phi$ satisfiable?

Below $\phi$ stands for a modal sentence. The question is to decide whether it is true that 1) if $\phi$ is satisfiable, then $\square \phi$ and $\diamond \phi$ are satisfiable, and 2) if $\phi$ is ...
1
vote
2answers
42 views

Categorical proof in natural deduction

I'm reading Fitch's book on Symbolical Logic and I don't understand how to prove, with natural deduction, that the following is a theorem without using any hypothesis. This is what is to be proven (...
4
votes
2answers
38 views

Natural deduction of (p->(p->q))->q on the hypothesis that p

I am struggling with natural deduction. I am doing the exercises in Fitch's book and now I am supposed to give an intelim proof of the theorem above (an intelim proof is one that uses only ...
0
votes
2answers
37 views

Give a categorical proof of p -> [q -> q]

I am doing Fitch's Exercises of Symbolic Logic, Chapter 1. This is the first exercise. We have so far axioms such as the distributivity axiom, the axiom of conditioned repetition, the transitivity of ...
0
votes
1answer
38 views

$\vdash\neg(\square \neg p\land p\land\diamond(p\land\square p\land \diamond p) )$

How to show that $\vdash\neg(\square \neg p\land p\land\diamond(p\land\square p\land \diamond p) )$ in the logic K? First of all, does this proof work? Assume the converse (i.e. that $\vdash\square \...
0
votes
0answers
29 views

How to simplify this formula in DNF?

Given a truth table, a formula in DNF was created, as shown below: (-p ^ -q ^ r) v (p ^ -q ^ r) v (p ^ q ^ -r) v (p ^ q ^ r) How would the simplification be represented? There are two r's, and two ...
0
votes
2answers
35 views

Boolean expression simplification - is my solution correct?

I have this boolean expression: (x′ ∧ y ∧ z′) ∨ (x′ ∧ z) ∨ (x ∧ y) and I simplified it using K-maps to this: (y ∧ z′) ∨ x Is my solution correct? Thanks!
2
votes
2answers
65 views

Modus Ponens - Implication vs Disjunction

The Modus Ponens inference rule is generally expressed as: $$ \begin{array}{rl} & P\rightarrow Q \\ & P \\ \hline \therefore & Q\end{array} $$ Is the below rule ...
1
vote
1answer
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, ...
0
votes
1answer
53 views

Russell's “propositional” paradox

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 ...
0
votes
1answer
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) ...
1
vote
1answer
48 views

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 ...
2
votes
1answer
40 views

How to think of formal derivation $\Gamma \vdash \phi$ in terms of trees/graphs?

According to my text, a finite set of formulas $\Gamma$ in a given language $L$ is derivable, denoted $\vdash \Gamma$, if $\Gamma$ belongs to the least collection of finite sets of formulas, denoted $...
0
votes
0answers
21 views

Propositional Logic Translation from sentence

I'm trying to translate below sentences to propositional logic but I don't know if my understanding of the main steps of translation are correct or not. I would like to ask for help to correct me. ...
0
votes
2answers
47 views

How can I convert this sentence to propositional logic (semantic and resolution)?

There were 3 people J, P, A. Only 2 people brought gifts to the party. If J brought a gift to the party, proof that P or A did not brought the gift. What I can think about this sentence is: $ J, P \...