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

Filter by
Sorted by
Tagged with
2
votes
1answer
26 views

Precedence between implication and bi-implication

I came across this question: Let p, q, and r be the propositions ...
1
vote
1answer
24 views

How to determine if given function is functionally complete

Given any random boolean function, is their any step wise procedure to find out whether it is functionally complete? The simplest approach I came across is this: We need to find whether given ...
1
vote
1answer
34 views

𝛾-rule in semantic tableaux of first-order logic

I'm a novice and I'm trying to understand semantic tableaux in First-Order Logic. 𝛿 - existential rule makes sense to me, if ∃x A(x) is true, saying "let c by ...
0
votes
2answers
33 views

Problem with formulating the negation of a statement

The excersise asks us to prove with an Indirect Proof that if $abc$ is an irrational number then at most two of $a,b,c$ are rational numbers. So we have, Let $P$ denote "$abc$ is irrational" and let ...
0
votes
2answers
37 views

First Order Logic: Diffrence b/w $\{\forall x P(x) \implies Q(x) \}$ and $\{ (\forall x P(x)) \implies Q(x)) \}$

There is GATE exam question which is confusing (in first look at least to solve): Which of the following first order formula is logically valid? Here $\alpha(x)$ is a first order formula with ...
2
votes
1answer
40 views

Interpretation of a valuation function when we have a known truth and an assumed truth in a proof

To provide context, I am currently learning about Conditional Introduction. This is the first time in this propositional calculus unit that I have encountered an assumed truth ; previously, all ...
1
vote
1answer
45 views

Trying to figure out how to use “proof related notations” correctly

Let $a$ and $b$ be positive numbers. Prove that $a+b=1$ if and only if $a=2t/(1+t) $ and $b=(1-t)/(1+t)$ for some number $t$, $0<t<1$. My Proof: Let $P$ denote: "$a=2t/(1+t) $ and $b=(1-t)/(1+...
1
vote
1answer
22 views

NEGATE this statement: if $L(M) = \emptyset$, then for any $w$, $M$ halts on $w$ implies $M$ loops on $ww$

if $L(M) = \emptyset$, then for any $w$, $M$ halts on $w$ implies $M$ loops on $ww$ M is a turing machine. my attempt First I'm trying to simplify this using $A \to B = not A \lor B$ $\...
3
votes
1answer
45 views

Reference for normalization of propositional logic natural deduction.

I'm looking for a reference for the normalization of classical propositional logic natural deduction. I have heard that D.Prawitz's book Natural Deduction is a good reference on the FOL. But first I ...
1
vote
0answers
35 views

Expression deduction algorithm in propositional logic

I need to find a way to deduce an expression in propositional logic. The given expression $\alpha$ contains up to $3$ variables. I need to find a list of hypotheses $\Gamma$ consisting only of ...
1
vote
1answer
40 views

Is the set of Valuation Functions finite?

I've been learning about interpretation functions and valuation functions. Intuitively, it seems as though there are an infinite number of Interpretation Functions, which I will denote as $I_n$. i.e....
0
votes
2answers
66 views

Natural deduction proof of $p \lor (p\implies q)$ with propositional calculus [closed]

I'm having a bit of trouble proving this with the propositional calculus rules. $$p \lor (p\implies q)$$ Would someone mind helping me and showing which rules they've used with an explanation! Thanks!...
0
votes
2answers
72 views

How to prove the distributive law for propositional logic without using truth tables or natural deduction.

I haven't learnt natural deduction yet so I'm completely stuck on how to proceed. One tip I was given was to use the properties of negation but again, that's not really helping.
2
votes
1answer
72 views

First-Order Logic: Formalisation of the phrase “Not all that glitters is gold”

I am trying to determine which of the following expressions are a valid formalisation of the phrase "Not all that glitters is gold". I have the following options: (1) ∃x. (𝖦𝗅𝗂𝗍𝗍𝖾𝗋(x)→𝖦𝗈𝗅𝖽(...
-1
votes
0answers
23 views

For what quantifiers will the statement (quantifier) x ∈ X : (quantifier) x ∈ X : P = (quantifier) x ∈ X : P be true?

For what quantifiers will the statement (quantifier) x ∈ X : (quantifier) x ∈ X : P = (quantifier) x ∈ X : P ? Is this true by derivation, or must this be an axiom? $$ $$ For example: $ $ $\forall x ...
1
vote
1answer
30 views

Defining Deductive Validity

I read the following: "The argument is deductively valid iff it is impossible for the all of the premises to be true and the conclusion false" Definitions like these strike me as describing what ...
6
votes
3answers
279 views

How does one visualize propositional logic?

I apologize if this is an under specified question, but I will try and provide some context. I am beginning to learn the foundations of propositional and predicate logic after starting a course in ...
2
votes
2answers
65 views

Compactness theorem for sentential logic

I am reading proof of compactness theorem for sentential logic in Enderton's book, A mathematical introduction to logic. (Compactness theorem) A set of wffs is satisfiable iff every finite subset ...
2
votes
0answers
52 views

Circular Induction

Question: Suppose you have a circle with equal numbers of 0’s and 1’s on it’s boundary, there is some point I can start at such that if and travel clockwise around the boundary from that point, I will ...
0
votes
1answer
34 views

Conversion of English Sentence into First Order Logic & Proof using rules of inference.

I am solving some problems from the book Discrete Mathematics & its applications with combinatorics & Graph Theory by Kenneth H Rosen. I have difficulty solving these three problems: Is the ...
1
vote
1answer
36 views

Reference: Beth Trees in Propositional Logic

I am looking for a reference on so-called ''Beth trees''. Take a finite set of propositional formulas $\mathcal{F}$. As an example, we might be looking for the set of valuations $v$ that satisfy ...
3
votes
1answer
84 views

Propositional Logic and Redundancy

There are Philosophical problems with the Material conditional. The Dutch philosopher Emanuel Rutten has written an article about it, titled: Dissolving the Scandal of Propositional Logic? From that ...
0
votes
1answer
68 views

How to know when every conclusion has been derived from a set of statements?

Let us say that we have 3 statements: 1. A>B 2. B>C 3.A From here, a total of 3 conclusions can be reached: ...
0
votes
1answer
49 views

Difference between $\exists x ( f(x) \rightarrow g(x) )$ and $\exists x ( f(x) \land g(x) )$?

For converting english statements to logical statements, I've understood that $\forall$ uses $\rightarrow$ and $\exists$ uses $\land$ (generally). I referred a particular question on this site, but I ...
3
votes
3answers
79 views

Is $\exists x P(x) \implies \exists x Q(x)$ Logical equivalent to $\exists x [P(x) \implies Q(x)]$

Is $\exists x P(x) \implies \exists x Q(x)$ Logical equivalent to $\exists x [P(x) \implies Q(x)]$? My intuition: Let Left hand side be $\exists x P(x) \implies \exists x Q(x)$ and Right hand ...
0
votes
2answers
24 views

Doubt in logical equivalence

I am beginner in mathematical logic. There is a statement in textbook(Discrete maths by Rosen) that for logical equivalence of 2 predicates, we need to show that both have same truth values(same true ...
2
votes
1answer
69 views

Doubt in logic theory [closed]

I am a beginner in mathematical logic. I found following which i did not understand 1) Addition logical implicative - $p \to (p \lor q)$ In explanation, he says if we know p, then we can add q. ...
0
votes
0answers
18 views

Algorithm to decide whether a proposition is constructively provable [duplicate]

To decide whether a propositional formula $P$ is classically provable, the completeness theorem gives an easy algorithm : simply test all finite boolean combinations of the variables of $P$. It is ...
0
votes
1answer
36 views

Proof confusion or solving strategy?

I was introduced to a $Claim X$ for which the proof involved the use of the Truth of $Claim Y$, later I found a proof to $Claim Y$ (from a different source) and was suprised to find that it involved ...
2
votes
2answers
71 views

How to designate that a proposition is semantically true?

The question is more about mathematical notation I guess. In logic we can designate that a conclusion $B$ is (syntactically) deducible from the premises $A$ by: $A_1...A_i ⊢ B$ If the above is true ...
5
votes
3answers
64 views

Need to prove $(p \land q) \land (\lnot p \lor r) \rightarrow (q \lor r)$ is a tautology.

I need to prove the following expression is a tautology using propositional logic laws. My current working out is as follows [not sure if it is correct]: $$(p \land q)\land ( \lnot p \lor r) \...
1
vote
1answer
43 views

Logic equivalents for connectives in SL using only the Sheffer stroke

According to forallx (P.D. Magnus, N.D.) every sentence written using a connective of sentential logic can be rewritten as a logically equivalent sentence using one or more Sheffer strokes $(A \mid B)$...
3
votes
2answers
58 views

Prove $A \implies C$

Given, $(A \lor B) \implies C$, prove $A \implies C$ My Proof: 1 By Conditional Exchange, $$\neg(A \lor B) \lor C$$ 2 By DeMorgan's Law, $$(\neg A \land \neg B) \lor C$$ 3 By Simplification, $$\...
4
votes
2answers
52 views

Prove $\neg (p \land q) \vdash \neg p \lor \neg q$ by natural deduction

I have tried solving this by negating $\neg p \lor \neg q$ to get to a pbc, but apparently you need to use a few lem's (law of excluded middle) to solve the problem. Where (and how) have I gone wrong ...
1
vote
1answer
54 views

$P → Q$ using only NOR gates [closed]

Not much to say apart from what's in the question. I'm fairly new to logic so help would be much appreciated.
-1
votes
0answers
32 views

Efficient way to create relationships between logical variables?

I'm not well versed in logic, but I know basic logical operators and the corresponding truth tables. My question is this. Given a set of n variables, how could I symbolically encode the relationships ...
2
votes
2answers
40 views

What's the most efficient way to convert any propositionnal logic formula to DNF

In every paper that I've read so far, authors say that they convert a formula into disjunctive normal form (DNF) but they don't give any detail on how they are doing it. The only way of converting a ...
0
votes
1answer
45 views

Prove $(\exists x)A\to((\exists x)(A\wedge(B\vee C))\equiv B \vee (\exists x)(A\wedge C))$, if $x$ is not free in $B$

Prove $(\exists x)A\to\big((\exists x)(A\wedge(B\vee C))\equiv B \vee (\exists x)(A\wedge C)\big)$, if $x$ is not free in $B$. I've tried multiple different ways and I'm not able to see a good path ...
1
vote
4answers
58 views

Prove that if P, then $Q → ¬(Q → ¬P)$

Suppose that $P$ is true. Prove that $Q → ¬(Q → ¬P)$ is true. My attempt: If $Q$, then statement $\lnot (Q → \lnot P)$ must be true. We know that $P$ is true. For $¬(Q → ¬P)$ to be true, $Q$ must be ...
2
votes
2answers
59 views

Prove using properties of logical equivalence $(P\wedge (P \to (Q \to R))) \to (Q \to R)$ is a tautology

Can anyone help me with this problem using properties of logical equivalence: Prove that $(P\wedge (P \to (Q \to R))) \to (Q \to R)$ is a tautology.
1
vote
2answers
57 views

Question: Is This a Proposition?

Every positive even integer can be written as the sum of two primes. The answer is: this is a proposition. Nobody knows its truth value, but it's unique. I wonder what is unique and why its ...
1
vote
2answers
49 views

Symbolic Logic Proof — Typo?

I was working through some proofs in my symbolic logic book when I came across the following problem: $$\text{Given:}$$ $$\\ (A \lor B) \implies(C \lor D)$$ $$\\ (C \implies W) \land (D \implies \neg ...
2
votes
1answer
67 views

Vacuous Truths and Continuity at a Point Where a Map is Undefined

I understand that a conditional statement is said to be vacuously true in the case that its antecedent is false, in which case the conditional statement is, itself, true. However, what about the ...
0
votes
0answers
24 views

Propositional formula proof by resolution

I am having issues with proving by resolution the follow propositional formula: $(ψ_1 ∧ ψ_2) → ψ_3$ where $ψ_1 = (p → (q ∨ r)) ∧ (q → (r ∨ p)) ∧ (r → (p ∨ q))$ $ψ_2 = ((p ∧ q) → r) ∧ ((q ∧ r) → p) ∧...
1
vote
0answers
28 views

How can I simplify this proposition where 4 out of 5 values are true and the remaining 1 out of 5 is false?

I am fairly new to logic and I am curious as to whether it is possible to simplify this proposition where 4 out of 5 values must be true and one of them has to be false. (P1 ∧ P2 ∧ P3 ∧ P4 ∧ ¬P5) ∨ (...
1
vote
1answer
76 views

How to formalize this simple problem in logic?

I want to translate this problem with a simple logical expression. Say that my system only accepts tuples of strings $(s=s_1...s_n$, $t=t_1...t_n)$ where $s_i$ and $t_i \in \{0, 1, 2\}$, that are ...
2
votes
4answers
40 views

Prove that $(\neg P \lor Q)\wedge (P \lor \neg R)\wedge (\neg P \lor \neg Q)$ and $\neg (P \lor R)$ logically equivalent.

Q. Prove that $(\neg P \lor Q)\wedge (P \lor \neg R)\wedge (\neg P \lor \neg Q)$ and $\neg (P \lor R)$ logically equivalent. I can get a feel for why this will be true. My argument goes as follows: ...
1
vote
2answers
58 views

Deduction of $\forall x(\neg p(x)\rightarrow q(x)), \forall z(p(z)\rightarrow r(z))\vdash \forall z(\neg r(z) \rightarrow\exists yq(y))$

I trying to study for my final exam and I can't figure out how to solve this: $\forall x(\neg p(x)\rightarrow q(x)), \forall z(p(z)\rightarrow r(z))\vdash \forall z(\neg r(z) \rightarrow\exists yq(y))...
1
vote
1answer
35 views

Can you replace any Statement in a Tautology?

A few theorems I read somewhere online say that in a tautology, you can replace any statement by another statement to get another tautology. For instance, we have the following tautology: $[A \land (...
0
votes
1answer
15 views

Absorption's Law - Negative proposition affects the law?

This is a simple question. It's known that the absorption's law is like the following example: p ∧ (p V q) = p But, if the proposition has a negation, does this affect the law? for example: p ∧...