Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
7 views

How to derive ~ ( P&Q) from ~ P using natural deduction?

Certainly if P is false, (P&Q) cannot be true. But how to prove this using natural deduction? I'd propose as a direct proof the following derivation : (1) ~P ( Premise ) (2) ~P v ~Q ( ...
2
votes
2answers
26 views

Logical Equivalences with English Statements

Showing two statements $p$ and $q$ are logically equivalent is to show $p \Longleftrightarrow q$. I understand this, however I think when looking at english statements showing whether or not they are ...
0
votes
1answer
22 views

Usage of adjective and imperative in statement logic

I think I know how to form sentences in statement logic if it's an "if statement" like (A) and (B) below, but how do I express adjective like "not so easy" or imperative like "Choose X or Y", as shown ...
0
votes
2answers
55 views

How to prove $\vdash p\to\neg\neg p$ in this system?

I was asked to prove $\vdash p\to\neg\neg p$ in this system. Axioms: $(\mathcal A_1)\vdash p\to(q\to p)$ $(\mathcal A_2)\vdash (p\to(q\to r))\to((p\to q)\to (p\to r))$ $(\mathcal A_3)\vdash \...
-4
votes
0answers
29 views
4
votes
1answer
100 views

Why are there several axiom systems for propositional logic?

There is an axiom system that I found in Elliot Mendelson's, "Introduction to Mathematical Logic", p.27, and Theodore Sider's, "Logic for Philosophy", p.59: (A1) P->(Q->P) (A2) (P->(Q->P))->(P->Q)->(...
0
votes
0answers
14 views

Graph Coloring in Propositional Logic

Let G be a legally colored graph with k colors; this means that each two adjacent vertices have different colors, and the total number of colors in G is k. In addition, the edges of the graph are ...
0
votes
1answer
36 views

Is the “ contrapositive relation” rigorously symmetric? What is rigorously the contrapositive of : ~X --> ~ Y?

Is the relation " being the contrapositive of" really symmetric? I mean : the contrapositive of X --> Y is ~Y --> ~X. If the relation " being the contrapositive of " is symmetric, then I can say ...
-1
votes
1answer
33 views

Semantics of exclusive or

How do I get a description of $\text {XOR}$ (exclusive or) only using the operators $\wedge$, $\vee$, $\neg$, $\rightarrow$ And is it possible to prove the correctness of such description?
1
vote
3answers
64 views

Natural Deduction Proof: A ↔ B |- (C → A) → (C → B)

In an attempt to prove the formula, I tried setting a hypothesis C -> A like the following ...
1
vote
2answers
81 views

Prove that the set $\{((p\to q)\lor r),(p\lor(q\lor s))\}$ is satisfiable?

Am I using the correct logic in my proof below? Rewriting the first element in the set using Logical equivalence involving Conditional statement yields: $(\neg p\lor q)\lor r$ – this can be further ...
1
vote
2answers
60 views

Prove $(((p\land q)\to r)\land(p \to q))\to (p \to r)$ is satisfiable.

I'm trying to learn how to apply shortcuts of a truth table, and was wondering if the following is correct: Let $A=(p\land q)$ Let $B = (A \to r)$ Let $C=(p \to q)$ Let $D=(B\land C)$ Let $E=(p \...
0
votes
1answer
24 views

Classical Propositional Logic and Axioms

We define a new proof system N over the connectors: {∨,¬} For every α and β- 𝐴1: (𝛼 ∨ (𝛽 ∨ (¬𝛼))) (axiom) Deductions: 𝑀𝑃1: if we have 𝛼, 𝛽 then we can deduce (¬(¬(α∨β))) 𝑀𝑃2: if we have (...
0
votes
2answers
21 views

Disjunctive normal form of (¬(p → q) → (q ∧ ¬r))

I learning how to convert to disjunctive normal forms, I have the following, (¬(p → q) → (q ∧ ¬r)) I understand any p→q can be represented as (¬p)∨q, therefore ...
0
votes
2answers
34 views

Please explain (p ∧ q) --> r and what the correct method to work this out is

I understand P ∧ Q, being that both must be equivalent, ie True & True, or False and False. I understand P --> Q implies that if P is True we know what Q is and if Q is true then the result is ...
0
votes
1answer
17 views

logical equivalence proof using propositional algebra

i need help to show that (p⇔r)⇒(q⇔r) is equivalent to ∼[(∼p∨r)∧(p∨ ∼r)]∨[(∼q∨r)∧(q∨ ∼r) using propositional algebra. I did it using truth tables but i am struggling with propositional algebra.
0
votes
0answers
10 views

Symbolize using schemas, quantifiers and logical connective.

How can I symbolize the follow sentence: "not all integers numbers are positive" I tried to do this: if x∈ℤ and P(x)= x>0 (∃x)¬p(x) Thanks in advance.
0
votes
0answers
36 views

Substitution for propositional logic

In the propositional logic, let the string $(a_1, a_2, \cdots, a_n)$ be WFF. And exist natural numbers $i< j\in \{1,2 \cdots, n\}$ search that string $(a_i,a_{i+1}, \cdots , a_j )$ is also WFF. ...
0
votes
1answer
38 views

How can I deny the formula $(\exists x)(p(x)\vee(\forall y)h(y)) \leftrightarrow q $

Can anyone explain me how can I deny this propositional formula? $$(\exists x)(p(x)\vee(\forall y)h(y)) \;\leftrightarrow\; q $$ According to my textbook, the answer would be: $$(\forall x)(\sim p(x)...
-3
votes
0answers
29 views

Natural Deduction proof prove (¬p v q) --> p ⊢ p [closed]

How would one combine all natural deduction rules for this proof
1
vote
2answers
70 views
2
votes
1answer
27 views

Is a statement with a quantified function variable considered to be of second-order logic?

Here $\mathbb{N}=\left\{n\in\mathbb{Z}:0<n\right\},$ function parameter lists are delimited as $\left[\dots\right],$ and $\underline{\exists}$ means there exists exactly one. One way to state ...
0
votes
1answer
16 views

Proving inequality equivalence using propositional logic: stuck with redundancy at the end of the proof + circularity problem

I would like to prove formally that : ~ ( a is less than b or equal to b) is equivalent to ( a is strictly greater than b ). But I cannot get rid of a redundant conjoint at the end of the proof. ...
2
votes
1answer
40 views

Is the last variable of any implicational tautology also the last variable of one of its premises?

I'll define my terminology via the following BNF grammar for implicational logical expressions: <clause> ::= "(" ...
1
vote
2answers
92 views

Is it true that the statement: “ $\frac{1}{0}$=5 is false statement ” is unprovable statement?

I had a conversation on this site about some question, and a claim had been made by one of the users on this site that the truth value of this statement(" $\frac{1}{0}$=5 is false statement " ) is ...
0
votes
1answer
33 views

An example of a maximal consistent set?

I an doing old exams, and there is an exercise that asks to give an example of a maximal consistent set, and while i understand the definition, I cant seem to find or come up with an example.
2
votes
1answer
47 views

How do I write equivalent formulas using only $\to$ and $\bot$?

for following formulas in propositional logic, how do I write equivalent formulas using only logical symbols → and $\bot$: $\alpha$ $\land$ $\beta$ $\alpha$ $\lor$ $\beta$ $¬\alpha$ Is it ...
0
votes
2answers
56 views

What does the fact that “~P is equivalent to (P --> ~P) ” tell us about the nature of logical falsity?

After all, what does " false" mean in logic? Does this fact: "~P is equivalent to (P --> ~P) " deliver the essence of logical falsity? I mean , does this formula express the idea that being false,...
2
votes
2answers
23 views

Velleman - Conditional truth table justification

Velleman's logic in sentence 3 under figure 4 is confusing me. He is using lines two and four of the truth table to infer what Q of line 1 should be. But lines two and four assume P --> Q are true ...
1
vote
4answers
89 views

Natural deduction proof: $A \vee (B \wedge C) ├ (A \vee B) \wedge (A \vee C)$

I assume that I need to set a hypothesis somewhere in the process, but I don't know how. ...
2
votes
1answer
47 views

Natural deduction proof: C Ʌ D, C ↔ E, D ↔ F |- E Ʌ F

Originally, when I tried to solve this problem for the first time, my answer was like the following. ...
1
vote
2answers
32 views

Natural Deduction proof: C Ʌ D, C ↔ E |- (C V F) Ʌ (D V F) Ʌ (E V F)

This is one of the tasks that I'm working on in Logic class of a CS degree program at University. The teacher just said to me that my answer was wrong, but she never told me when I asked her where I ...
4
votes
2answers
65 views

Are “ replacement rules” and “ inference rules” ( in natural deduction) really two kinds of rules?

I think the distinction, in natural deduction systems, between " inference rules" and " replacement rules" is standard. ( For example, Bergmann, The Logic Book). Is " replacement rule" anything ...
0
votes
1answer
44 views

Is there a general and mechanical method to solve algebra of sets (or alg.of propositions) equations?

In some simple cases it seems possible to solve for X a set equation. For example, if I am given : X Inter U = U , and knowing the law according to which S Inter U = S for any set S, I can find ...
1
vote
0answers
55 views

“Truth set” approach to validity and logical consequence: how does it relate to the standard approach? what are the possible drawbacks?

References : I think the " truth set approach" to validity and logical consequence can be linked to the name of R. Carnap ( who defines L-truth and L-implication in this way in his Introduction to ...
0
votes
0answers
6 views

Prove that $\hat{\alpha}$ is a base of $2^\mathbb{P}$

Let it be $\mathbb{P}$ a set of propositional letters and $\phi$ a set of formulas generated by $\mathbb{P}$. Consider the space $2^{\mathbb{P}}$ with the product topology, and define for every ...
2
votes
1answer
55 views

If every truth assignment satisfies some wff, some finite disjunction is a tautology

Let $X_1,X_2,X_3,...$ be well formed formulas. If for every truth assignment $v$ there exists $n$ with $X_n$ satisfied by $v$, show there exists $n$ with $X_1\lor...\lor X_n$ a tautology. We can ...
2
votes
1answer
33 views

Help me with this propositional logic demonstration

This is a simple propositional logic demonstration. I’d appreciate your help. I don’t know if my answer is correct, but the textbook used another demonstration. The question $T \vee R$ $(T \vee R) \...
0
votes
3answers
42 views

Is $(p \lor q) \to (\neg p \to (p \lor q))$ a tautology?

This question came up in a recent assignment. I was asked to find a logically equivalent alternative to the statement in the title from the options below. (p ∨ q) ∨ ¬p (¬p & ¬q) ∨ (p ∨ q) (p &...
0
votes
1answer
40 views

In a truth table, does a row represent technically an interpretation , or a subset of the whole ( infinite?) collection of possible interpretations?

I would like to understand more precisely the relation between the basic truth table method to test validity of formulas (and of reasonings) and the more advanced set theoretic definition of validity ...
4
votes
0answers
53 views

Is the consequence relation of a finite set of boolean connectives finitely generated?

Let $S$ be the set of all n-ary functions on $\{0,1\}$ for all n, including the 0-ary functions. Let $F$ be a finite subset of $S$. Consider a countably infinite set of propositional constants $PROP$. ...
2
votes
1answer
68 views

Can we prove this proposition without thinking semantics?

Let $A$ be a set of propositional symbols, $\alpha$ ba a WFF on $A$ and $M$ be a subset of $A$. And let $M^+: = M \cup \{(\neg a): a\in (A-M)\}$. Then, only one of $M^+ \vdash \alpha$ or $M^+ \vdash ...
3
votes
1answer
89 views

Distributing locks and keys so certain subsets of people can open all locks

A vault can be opened by n number of keys. Five people, A, B, C, D, E are given some of the keys. Each key can be duplicated arbitrary number of times. Find the smallest number n and the distribution ...
0
votes
1answer
29 views

Circle symbol for true logical statements?

I am reading the book Introduction to Higher-Order Categorical Logic by Lambek and Scott, and have run across this inference rule when they define what they call the "conjunction calculus": $$A \...
1
vote
0answers
38 views

Can we use induction on the number of connectives?

Usually when we prove some properties of propositional formulas, we use induction on the complexity of propositional formulas, but instead, we can just use induction on the number of occurrence of ...
0
votes
3answers
40 views

Prove that a sentence is tautology, satisfiable but not tautology or unsatisfiable

I am trying to understand how to determine whether a sentence is a tautology, satisfiable but not tautology or unsatisfiable using the right approach Example: (¬up → ¬down) → ¬up I tried the ...
4
votes
3answers
80 views

Prove $\vdash (A_1 ↔ A_2) \vee (A_2 ↔ A_3) \vee (A_3 ↔ A_1) $ using natural deduction.

I think this is true. Because by the pigeon hole principle, Two of $A_1, A_2, A_3$ must have the same true value. But I have no idea how to prove it.. Can somebody help me? Of course, we can use ...
0
votes
0answers
24 views

SATisfaction for equivalent formulas

Pardon any errors in my usage of terminology; my background in mathematics is much weaker than it should be. I'm working on a project about the conversion between forms of temporal logic (namely LTL ...
0
votes
2answers
44 views

Symbolizing Circular Logic

A general case of circular logic is when you have an assumption $P$, and $Q$ serves as ‘proof’ for $P$, but the only reason $Q$ is said to be true is because of $P$. In other words, the proof for $P$ ...
0
votes
3answers
46 views

Interpretation of logic equivalence: $P\rightarrow Q\Leftrightarrow \sim P\vee Q$ [duplicate]

My logic textbook defines the notion of logic equivalence as: A proposition $P$ is logically equivalent to a proposition $Q$ (written $P\Leftrightarrow Q$) when the biconditional $P\leftrightarrow Q$ ...