Mathematics

Questions tagged [propositional-calculus]

Ask Question

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

4,524 questions
Newest
Active
Bountied
Unanswered
Filter by
Sorted by
Tagged with
0
votes
0answers
26 views

How to show that a valid rule is not derivable in intuitionistic propositional calculus.

First a word on notation, let the following be an inference rule that takes $\Gamma$ (a set of well-formed formulas) as premises and has $\psi$ (a well-formed formula) as a conclusion. This is ...
0
votes
1answer
22 views

Expressing “For every positive integer $a$, there exists an integer $b$ with $|b| < a$ such that $|bx| < a$ for every real number $x$” symbolically

I would like to express For every positive integer $a$, there exists an integer $b$ with $|b| < a$ such that $|bx| < a$ for every real number $x$ symbolically. My attempt: For every positive ...
0
votes
1answer
24 views

How can I know when to negate quantifiers when taking the contrapositive of a statement?

Continued from a question I asked here, since I believed this question deserves its own thread. When taking the contrapositive, I was taught to negate the quantifiers as well. For example, if we have ...
-1
votes
1answer
26 views

Contrapositive of: If $a$ is a real number such that $|a| < r$ for every positive real number $r$, then $a=0.$

I wish to state the contrapositive of: If $a$ is a real number such that $|a| < r$ for every positive real number $r$, then $a=0.$ First, I want to state the original statement symbolically. $\...
2
votes
1answer
62 views

Is disjunction elimination a more general form of modus ponens?

It seems to me that disjunction introduction and disjunction elimination implies modus ponens. To be clear, I'm defining disjunction introduction as: $$p\vdash (p\lor q)$$ disjunction elimination as: $...
2
votes
1answer
50 views

For $x \in \Bbb R$, for all $y (|y|<x \implies y<5)$

Given that $x$ is a free variable beloging to the set of real numbers, find the set of values for $x$ for which the following statement is true: $\forall y (|y|<x \implies y<5)$ My attempt: If $...
2
votes
1answer
60 views

Contrapositive of: If $a_n > 0$ and $\sum a_n$ converges, then $\sum 1/a_n$ diverges.

I would like to find the contrapositive of: If $a_n > 0$ and $\sum a_n$ converges, then $\sum 1/a_n$ diverges. My first idea is to rewrite it symbolically: Let $a_n$ be a sequence of real numbers. $...
0
votes
0answers
30 views

How does a negation distribute when a statement is expressed in words?

Consider the following implication: Let $x,y,z$ be integers. If exactly two of the three integers $x,y,z$ are even, then $3x + 5y + 7z$ is odd. The contrapositive of the statement above would be: ...
0
votes
1answer
16 views

resolvent clause theory

This is about correctness of resolution lemma Let R be a resolvent of two clauses $C_1$ and $C_2$. Then $C_1, C_2 \models R$. Proof By definition $R = (C_1 āˆ’ \{L\}) \cup (C_2 āˆ’\{\bar{L}\}) $ (for some ...
-4
votes
0answers
36 views

Simplify $¬¬qāˆ§T$ to get $q$. [closed]

I am having issues understanding how to use the laws of propositional logic. Simplify $Ā¬Ā¬qāˆ§T$ to get $q$.
-4
votes
1answer
26 views

Negation of $(p\to\neg q)āˆ§\neg p$ [closed]

can someone please help me out with the negation of the following: $(p\to\neg q)āˆ§\neg p$ I keep getting confused at mid-way, so I'd appreciate a step-by-step approach. Thanks!
1
vote
1answer
52 views

Using Truth Tables to Solve Logic Riddles

I've been traversing the practice exercises in Kenneth Rosen's Discrete Math and Its Applications in preparation for an upcoming class that is heavily proofs-based. Constructing truth tables from ...
0
votes
3answers
35 views

Simple Logical Simplification - Distributive Law

I can't seem to understand the hopefully simple step of getting from : $(a \land b \land c) \lor (a \land b \land \lnot c)$ to: $(a \land b) \land (c \lor \lnot c)$ This step is in the answers and ...
0
votes
1answer
30 views

How to prove that propositions are not logically entailed?

Let's consider the next proposition: Aā‡”BāŠØAāˆØB I used a truth table to show that there exists model1={A=False, B=False} where (Aā‡”B) is True but (AāˆØB) is False. It means Aā‡”B does Not entail AāˆØB. Can you ...
0
votes
1answer
25 views

Does (A and B) entails (A if and only if B) and what is intuition?

Is the next statement correct: (Aāˆ§B)āŠØ(Aā‡”B) ? Formal definition of entailment is this: Ī±āŠØĪ² if and only if, in every model in which Ī± is true, Ī² is also true. I used a truth table to show that there is ...
0
votes
1answer
45 views

A small question concerning the correctness of induction

I think I've read enough about the Peano axioms and I also checked the similar posts here on StackExchange, but all I want to know is why induction can't be validated for all n by writing down the ...
2
votes
1answer
37 views

Is this a correct translation from english into symbolic logic? [duplicate]

"You can fool some of the people all of the time, and you can fool all of the people some of the time, but you canā€™t fool all of the people all of the time." (Abraham Lincoln) Let $P$ be &...
1
vote
1answer
33 views

Choice of postulate 1b in Kleene's Introduction to Metamathematics

In Introduction to Metamathematics, Kleene introduces a formal system where the first three postulates in the group for propositional calculus are: $$ 1a. A \to (B \to A)\\ 1b. (A \to B) \to ((A \to (...
2
votes
2answers
37 views

Negation of specific statement

Definition: We say that $X\subset \mathbb{R}$ is bounded above if $\exists C\in \mathbb{R}$ s.t. $\forall x\in X$ we have $x\leq C$. $(X \ \text{is bounded above}):=\exists C\in \mathbb{R}((\forall x\...
0
votes
1answer
36 views

An element is either in a set or not in a set

Is there a name for the following obvious fact? Given any set $S$ and any object $s$, either $s \in S$ or $s \notin S$.
4
votes
2answers
112 views

Prove that a wff built up only with $\lnot$ and $\leftrightarrow$ is a tautology iff $\lnot$ and each statement letter occur an even number of times.

First of all, I know how to prove this theorem below: A statement form that contains $\leftrightarrow$ as its only connectives is a tautology iff each statement letter occurs an even number of times....
1
vote
1answer
54 views

How can something true follow from a false proposition? [duplicate]

Trying to wrap my head around conditional statements/implication and the respective truthtable in propositional logic. Read a number of the related posts on here. I understand that there is no causal ...
0
votes
1answer
90 views

Proving that $\mathscr B$ is a tautology iff $\lnot \mathscr B'$ is a tautology using induction.

I have the following logic question about duality:(Introduction to mathmatical Logic by elliot mendelson , exercise $1.30$) If $\mathscr B$ is a statement form involving only $\lnot$ , $\land$, and $\...
0
votes
1answer
32 views

Clarification of a logical deduction example

I would like to ask for some clarification on an assignment of logical deduction. Specifically, the question is Which of the following are logically correct deductions? and below is an example: If an ...
2
votes
0answers
59 views

Showing that $\mathscr B$ is a tautology iff $\lnot \mathscr B'$ is a tautology.

I have the following logic question about duality:(Introduction to mathmatical Logic by elliot mendelson , exercise $1.30$) If $\mathscr B$ is a statement form involving only $\lnot$ , $\land$, and $\...
0
votes
2answers
50 views

Not understanding the meaning of a logic question.

I am trying to understand the meaning of this exercise question in a logic textbook. For each of the following statement forms,find a statement form that is logically equivalent to its negation and ...
6
votes
1answer
194 views

Is XOR-SAT + $2$-SAT in P?

I read in a paper a proof where you can reduce a $3$-SAT problem into $2$-SAT + HORN-SAT clauses. $2$-SAT + HORN-SAT is therefore, NP-complete. $2$-SAT, HORN-SAT, DUAL HORN-SAT, XOR-SAT are all in P. ...
-2
votes
0answers
19 views

find a proposition f that makes the s tautology

i) s= ((f āˆ§ q) ā†’ Ā¬p) ā†’ ((p ā†’ Ā¬q) ā†’ f) ii) s = ((r ā†’ (Ā¬qāˆ§p)) ā†’ f) ā†’ (fāˆ§(p ā†’ q)āˆ§r). started using DNF, select the solutions where s=t, and then get DNF for f only for these rows. Is this ok?
-1
votes
0answers
38 views

Can not verify the steps of this proof following the laws at each step

I am reading a proof structure of showing that ~true = false It is based on the laws of negation i.e. ~p = p = false Please note ...
0
votes
1answer
26 views

Solution without truth tables

Find all the estimations that show that the following is false. $(x \land y)\lor (x\land z)\lor(y\land z)\lor(u\land v)\lor (u\land w)\lor(v\land w)\lor(\neg x\land\neg u)$. I know how to solve this ...
0
votes
3answers
43 views

How to simplify $(\lnot p \rightarrow \lnot q) \land p$ and match the right statement?

The problem is as follows: "If Maria does not leave her house then she does not catch a cold, but Maria leaves her house" is equivalent to: I. Maria does not leave her house. II. It is not ...
-3
votes
1answer
41 views

If $[(p\rightarrow\ q)\land (\lnot p \rightarrow \lnot r)]\rightarrow (\lnot q \rightarrow r)$ is false how to find its equivalent in other words?

The problem is as follows: Assume the statement which is written below is false, ...
-1
votes
1answer
46 views

How to establish the truth values of a set of statements which depend on $\lnot p \rightarrow (q\lor \lnot r)$ when its false?

The problem is as follows: First find the truth values of $p$, $q$ and $r$ such as the complex statement from below is false. $$\lnot p \rightarrow (q\lor \lnot r)$$ Then using this information find ...
0
votes
1answer
88 views

Connective symbol similar to implies, but acts like And

This feels like a basic question or a misunderstanding, but I'm struggling to identify a simple concept having to do with the provability of an argument or proof. Imagine you have a proof that is well-...
0
votes
2answers
56 views

How to find the profit earned from getting right a set of logic statements?

The problem is as follows: Diana offers her sister Maria $3$ bitcoins for each true statement and $4$ bitcoins for each false that she finds correctly in the statements shown, where $\mathbb{Z}$ is ...
2
votes
1answer
36 views

Simplifying $[\{(\lnot p\lor q)\land(\lnot q\lor p)\}\to\{(q\lor\lnot p)\land p\}]\to[(p \leftrightarrow q)\lor(q \bigtriangleup p)]$

Simplify the following expression: $$\left[\{(\lnot p \lor q)\land(\lnot q \lor p)\}\rightarrow\{(q \lor \lnot p)\land p\}\right]\rightarrow\left[(p \leftrightarrow q)\lor(q \bigtriangleup p)\right]$$ ...
2
votes
2answers
28 views

Intuitive logic behind the following equivalences in propositional logic

I was going through the text Discrete mathematics and its applications by Kenneth H. Rosen where I came across few logical equivalences as follows: $1. (pā†’q)āˆ§(pā†’r)ā‰”pā†’(qāˆ§r)$ $2. (pā†’r)āˆ§(qā†’r)ā‰”(pāˆØq)ā†’r$ $...
1
vote
1answer
29 views

Can an assumption be discharged without it being part of the tree?

Given the following formula, use natural deduction to prove that it holds. The answer given by the professor was the following below: I would like to understand how we can discharge the assumption ...
0
votes
0answers
23 views

stuck on logic and propositional calculus problem

1.Show that $\neg((\neg p\land q)\lor(\neg p\land \neg q))\lor(p\land q)\equiv p.$ $\neg((\neg p\land q)\lor(\neg p\land \neg q))\lor(p\land q)\equiv \neg(\neg p\land ( q\lor \neg q))\lor (p\land q)\...
2
votes
1answer
46 views

What Percentage of Formulas in Propositional Logic is Satisfiable?

Let $P_{n}$ be the set of all formulas in propositional logic with $n$ variables. Let then $Q_{n} \subset P_{n}$ be the maximal set of all non-equivalent formulas in propositional logic of length $n$. ...
2
votes
1answer
29 views

Prove that {A ā‡’ ¬C, ¬A ā‡’ B} āŠ¢ C ā‡’ B using only Modus Ponens, the typical theorem (A ā†’ ¬C) ā†’ (C ā†’ ¬A) and 3 axioms.

I have an exercise where I have to prove the given sentence {A ā‡’ Ā¬C, Ā¬A ā‡’ B} āŠ¢ C ā‡’ B using only Modus Ponens, the typical theorem (A ā†’ Ā¬C) ā†’ (C ā†’ Ā¬A) and the following three axioms: Aā†’(Bā†’A) (Aā†’(Bā†’C))ā†’...
0
votes
1answer
73 views

Sum of symbol values in wff written in polish notation.

So I am currently dealing with a problem like this: If we count $\rightarrow , \land , \lor$ and $\leftrightarrow$ each as $+1$ , each statement letter as $-1$ and $\lnot$ as $0$ , prove that an ...
3
votes
0answers
57 views

Reasoning about “implies” truth table. [duplicate]

I am trying to find a reasoning for the truth table of $A \rightarrow B$ .Here is what I came to so far. $1.$ We have to first assume that if something can't be proven wrong , then it is true. $2.$ $A ...
-1
votes
0answers
39 views

How to find an atom which is not in a countably infinite set?

Suppose that a countably infinite list of propositional atoms $\mathcal{A}$. The resulting logical language is denoted $\mathcal{L}$. We write $K$ for a countably infinite set of formulas over $\...
1
vote
1answer
49 views

Prove “If $\{R, Q\} \vDash P$, then $¬P \vdash \lnot Q \lor \lnot R$”.

Using the book Dirk van Dalen. "Logic and Structure (Universitext)" as reference text. Decide whether the following statement is true or false, justifying the answer. If $\{R, Q\} \vDash P$,...
0
votes
0answers
57 views

Confusion about restoration of parenthesis.

In "Introduction to Mathematical Logic" by Elliot Mendelson , page $11-12$ , There is a passage about the restoration of parenthesis . As a example: $1. B \rightarrow \lnot\lnot A$ $2. B \...
1
vote
1answer
31 views

proof pierce law using contradiction [duplicate]

how to proof pierce law using contradiction $((a -> b) -> a) -> a$ ? $((a -> b) -> a) -> ~a$ $((a \lor a) \land (\neg b \lor a) -> \neg a$ please help pierce law proof using ...
0
votes
0answers
32 views

Logic question with premises

Put the following syllogism into the standard form, which uses a horizontal line to separate premises and conclusion. Moreover, tell whether it is valid or not by showing its Venn Diagram. Bill didn't ...
-2
votes
1answer
44 views

Having problems this proof [closed]

Suppose that $\phi$ proves if $\alpha$ then $\neg\beta$ and that $\phi$ proves $\beta$. Can we infer anything from $\phi$?
0
votes
0answers
7 views

Proof techniques for Łukasiewicz's propositional axioms {CCpqCCqrCpr, CCNppp, CpCNpq}

When I learned propositional calculus in school I was taught Łukasiewicz's third axiom system (https://en.wikipedia.org/wiki/List_of_Hilbert_systems#cite_ref-Pro_I_1-2): $$a ā†’ b ā†’ a$$ $$(a ā†’ b ā†’ c) ā†’ (...

1
2 3 4 5
ā€¦
91