Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.

learn more… | top users | synonyms (1)

0
votes
1answer
29 views

First Order Logic Question

$\forall x\ \forall y\ P(x,y) \to \forall x\ \forall y\ P(y,x)$ Is this a tautology? Is there a set method that we can use to find whether a wff is a tautology?
0
votes
2answers
45 views

Solving Logical equivalence & propositional logic problems without truth tables

I have no particular "Logic question" in hand at the time being, but need help to understand a way that can be used to prove "Logical equivalence without using truth tables". moreover can we solve ...
0
votes
2answers
34 views

Solve it by using logical proposition

Show that given logical proposition is tautology $((A \implies C) \land (B \implies C) \land \lnot C) \implies \lnot (A \lor B) $ I can apply the implication rule first and got $\lnot((A \implies ...
8
votes
6answers
2k views

Help to understand material implication

This question comes from from my algebra paper: $(p \rightarrow q)$ is logically equivalent to ... (then four options are given). The module states that the correct option is $(\sim p \lor q)$. ...
2
votes
1answer
30 views

How Do You Show That There Exist Infinitely Many Organic Tautologies?

This question takes inspiration from this question. A tautology is organic if none of it's proper sub-formulas are tautologies. In other words, if all of the sub-formulas excluding the formula ...
0
votes
0answers
9 views

Basic Predicate & Quantifier Doubt

Which one of the following well formed formulae is tautology? (A)∀x∃yR(x,y)<=>∃y∀xR(x,y) (B)(∀x[∃yR(x,y)=>S(x,y)])=>∀x∃yS(x,y) (C)[(∀x∃y(p(x,y)=>R(x,y))]=>[∀x∃y(¬p(x,y) V R(x,y)] ...
0
votes
1answer
39 views

Proof of formulas in sequent calculus

Is there an algorithm for proof of formulas in sequent calculus, like resolution method? I'm especially interested in natural deduction. UPDATE Well, we have one scheme of axioms $$\Phi\vdash\Phi$$ ...
2
votes
3answers
3k views

What is Validity and Satisfiability in a propositional statement?

I tend to see these words a lot in Discrete Mathematics. I assumed these were just simple words until I bumped into a question. Is the following proposition Satisfiable? Is it Valid? $(P ...
2
votes
1answer
41 views

Can we see natural deduction rules as functions or even as formal grammars?

Is there a way of seeing natural deduction rules as functions or even as formal grammars, maybe context-free grammars or Lambek grammars? It seems quite "easy" to see the rules as functions which take ...
0
votes
2answers
56 views

Prove $(p \rightarrow q) \land (r \rightarrow s) \implies ( \neg p \lor \neg r \lor q \lor s)$

$$((p \rightarrow q) \land (r \rightarrow s))\rightarrow ((p\land r)\rightarrow (q\lor s))$$ I have some problem with formula: $$(p \rightarrow q) \land (r \rightarrow s) $$ $$\equiv(\neg p \lor q) ...
2
votes
1answer
4k views

Finding Satisfiability, Unsatisfiability and Valid well formed formula

I have a confusion regarding how to check whether a wff is satisfiable, unsatisfiable and valid. As far as I understood, valid means the truth table must be a tautology, otherwise it is not a valid ...
2
votes
1answer
32 views

If $\Sigma$ is finitely satisfiable, can both $\Sigma \cup \{ \phi\}$ and $\Sigma \cup \{ \neg \phi\}$ be finitely satisfiable?

In propositional logic, if $\Sigma$ is finitely satisfiable, can both $\Sigma \cup \{ \phi\}$ and $\Sigma \cup \{ \neg \phi\}$ be finitely satisfiable? I proved that at least one of $\Sigma \cup \{ ...
2
votes
3answers
46 views

Logical Equivalence

Prove that p $\rightarrow$(q$\rightarrow$p) is logically equivalent to $\neg p$ $\rightarrow$(p$\rightarrow$q) without using truth table. It is easy to show that both the statements are tautologies. ...
0
votes
1answer
18 views

Is $ R = \{ (A,B) \in \Omega² \quad| \quad A \land B \} \quad$ with $\Omega = \{ A\quad| $ A is a proposition $ \}$ reflexive?

Is $ R = \{ (A,B) \in \Omega² \quad| \quad A \land B \} \quad$ with $\Omega = \{ A\quad| $ A is a proposition $ \}$ reflexive? I assume that you have to consider untrue propositions, too. $A \land ...
12
votes
1answer
170 views

Representing predicate logic as arithmetic

Summary Since the below is quite long, I thought I'd add this summary. Given the following: A statement in proposition logic can be converted to an arithmetic expression over the integers modulo ...
1
vote
0answers
22 views

Does a Length Always Exist such that a Tautology Always Exists Beyond That Length?

Suppose we have some set of fixed connectives such that tautologies exist and we write everything in Polish notation. The length of a WFF consists of the number of symbols that it has. WFFs can get ...
6
votes
5answers
822 views

What is a constructive proof of $\lnot\lnot(P\vee\lnot P)$?

Glivenko's theorem says that $\lnot\lnot P$ is a theorem of intuitionistic logic whenever $P$ is a theorem of classical logic. Is it closely related to the so-called Gödel–Gentzen negative translation ...
-1
votes
2answers
31 views

Finding a morphism from one boolean expression to another i.e. $\phi :(x \Rightarrow y) \rightarrow (y \vee z)$

What I would like to do is figure out how to get from $(x \Rightarrow y) $ to $ (y \vee z)$, that what I could AND or OR to $(x \Rightarrow y) $ so as to give $ (y \vee z)$. Breaking this down I ...
1
vote
1answer
15 views

Constructing a tautology given a set $\Sigma \subset $Prop(A) with special properties.

I am trying to follow Logic Notes of Lou Van Dries and I am stuck at a particular question in propositional logic. Assuming $A$ is any set and Prop$(A)$ is the set of propositions on $A$. The ...
-3
votes
4answers
77 views

Prove that $(\neg p \wedge \neg q) \vee (p \wedge q) \equiv (\neg p \vee q) \wedge (\neg q \vee p)$ [closed]

Prove that $(\neg p \wedge \neg q) \vee (p \wedge q) \equiv (\neg p \vee q) \wedge (\neg q \vee p)$. I need to prove it by using equivalent sentences.
1
vote
1answer
34 views

Logic normals forms, wolfram, problem.

This is formula which I must write as CNF, DNF and Negation of formula as CNF and DNF: $$(p \rightarrow (q \rightarrow r)) \rightarrow ((p \rightarrow \neg r) \rightarrow (p \rightarrow \neg q))$$ ...
1
vote
3answers
42 views

When I can reverse the logical operators?

I heard say that is logically equivalent to say it: $$\neg (p \vee q) = p \land q$$ So every time you have a negation operator in front can make a "distributive" altering the operator from within? ...
0
votes
1answer
27 views

Logical implications in classic logic

I have the following problem: If Joseph is playing piano or Joaquim is playing guitar, then John is not sleeping. I perfectly understood the situation but didn't understand the second row of ...
1
vote
0answers
26 views

Proving strong completeness of propositional logic by assuming weak completeness via algebraic methods.

In logic via algebra (page $93$), Halmos tries to prove strong completeness ( if $S\models q$ then $S\vdash q$) assuming weak completeness ( if $q$ is a valid in the Boolean logic $(A,F)$ then $q\in ...
2
votes
1answer
48 views

Universal quantifier question: $(\forall x)[x < 0 \Rightarrow x^2 > 0]$

Universal quantifier question: $(\forall x)[x < 0 \Rightarrow x^2 > 0]$. Given the above expression, For all of $x$ [ if $x$ is less than zero, then $x^2$ is greater than zero]. Is that a ...
1
vote
1answer
39 views

Find the murderer by using truth table for formal logic (formal disjunction or formal implication)

I'm studying formal logic and i was wondering if you can check whether I've solved this task correctly. TASK. Two people are arrested as suspects for a murder case, Stan and Peter. Four witnesses ...
2
votes
3answers
58 views

is this proposition (inference) valid?

Is this inference valid or invalid? Why and how to prove this kind of question? $$p \rightarrow q, \neg q \rightarrow r , r \vDash p $$ Would a single truth table be enough for all types?
0
votes
1answer
26 views

Disjunction Elimination Proof

P∨(Q∨R) ⊢ Q∨(P∨R) Proof: 1.) P∨(Q∨R) Assumption 2.) P Assumption 3.) P∨R 2.) Disjunction Introduction 4.) Q∨(P∨R) 3.) Disjunction Introduction 5.) Q∨R Assumption 6.) Q ...
8
votes
4answers
680 views

Is the following a valid mathematical statement?

For all $f:\mathbb N\to\{1,2,3,\ldots,100\}$, If $f$ is a one to one correspondence, Then $f^{-1}(2)=3$ It seems as though this should not be a valid statement, since the implication fails to ...
5
votes
3answers
56 views

Difference between Gentzen and Hilbert Calculi

What is the difference between Gentzen and Hilbert Calculi? From my understanding from the reading of Rautenberg's Concise Introduction to Mathematical Logic, Gentzen calculus is based on sequents ...
2
votes
2answers
70 views

Difference between Logical Axioms and Rules of Inference

What's the difference between Logical Axioms and Rules of Inference? In my understanding, both are ordered pairs of formulas which are used to reach a conclusion through syllogisms. My questions ...
0
votes
2answers
20 views

Substitutions as mappings from the set of Propositional Variables to the set of Formulas

Rautenberg defines substitutions in propositional calculus as follows: " A (propositional) substitution is a mapping σ : PV →F that is extended in a natural way to a mapping σ : F → F " PV: set of ...
1
vote
1answer
44 views

Are there any consistency proofs for propositional or first-order logic?

Take for example the Hilbert-style axiomatizations of the propositional and first-order calculus. Since a crucial point when operating with a proof system is that no contradictions must be found in ...
0
votes
1answer
14 views

Epress $\exists! x P(x)$using universal quantifications, existential quantifications and logical operators

Epress the quantification $\exists! x P(x)$, using universal quantifications, existential quantifications and logical operators. Does anyone have an idea?
-1
votes
1answer
35 views

Difference between DNF and CNF

I'm stuck on a particular question, about Propositional Logic. Let $A$ be the propositional formula $((\lnot p \rightarrow q) \leftrightarrow\ (\lnot q \rightarrow \lnot r))$. Find a propositional ...
1
vote
1answer
42 views

$(Ǝx)H(x) \dashv \vdash (Ǝy)H(y)$?

I can prove the statement using the natural deduction, but I keep getting confused about this sequent, so it would be very thankful if someone can help me to understand this concept of predicate ...
3
votes
1answer
53 views

No truth function that is expressed by a formula that uses only implication and equivalence connectives

I proved the following statement by induction: Let $A$ be a propositional formula which uses only the connectives $→$ and $↔$. Prove (by induction on the complexity of $A$) that if every ...
0
votes
2answers
72 views

Prove propositional logic by resolution.

Prove $$[(p→q) \wedge (qr→s)]\to [pr→s],$$ which is the same as $$[(\lnot p\lor q) \wedge (\lnot (qr) \lor s)]\to [\lnot (pr) \lor s]$$ I believe it can just be done with algebra rules, but I got ...
2
votes
1answer
56 views

Lindenbaum-Theorem only concerning sentential logic provable in ZF?

Is the Lindenbaum-Theorem of sentential logic (= propositional logic) provable in ZF (i. e. without the axiom of choice)? Lindenbaum's theorem of sentential logic states that every set $\Sigma$ of ...
1
vote
1answer
42 views

Proving by induction on the length of a propositional formula?

I'm having a little trouble understanding the following proof question because I'm unsure what defines the 'length' of a propositional formula, I've seen multiple definitions whether it's the number ...
1
vote
1answer
18 views

Writing in disjunctive normal form using logical laws

I'm having trouble converting the below formula to disjunctive normal form using logical laws. I found the DNF using truth tables but I am having issues using just logical laws. Here is the formula: ...
0
votes
0answers
35 views

Finding a truth function

I wanted to find a truth function $f$ if it exists that make the formula below true: $((p\to \lnot(q \oplus \lnot p)) \to (\lnot r \oplus (q \to p)))$ Where the $\oplus$ operator is defined as: ...
1
vote
1answer
82 views

Proving $\vdash (p\to q)\lor (q\to r)$ using natural deduction

I'm trying to prove the following: $\vdash (p\to q)\lor(q\to r)$ using only intuitionistically valid rules. I've tried a few different ways, and I think my problem is that I'm not sure what ...
1
vote
1answer
451 views

proof of validity of tautology in first order logic

Every first-order logic formula which has a tautological shape in propositional logic is a valid formula. Will it be possible to give a formal proof for the above ? Thanks and Regards.
1
vote
3answers
33 views

Showing tautology without a truth table.

Show that the conditional statement is a tautology without using a truth table. $a)$ $(p \wedge q) \rightarrow p$ My suggestion would be getting rid of the implication first, so $(p \wedge q) ...
0
votes
0answers
21 views

Some computations in propositional calculus

I have some expressions of the form. I want to express them as $\bigvee (\bigwedge v_i)$. These are: 1) $(v_1 \vee v_2) \wedge (v_3 \vee v_4 \vee v_5)$ 2) $(v_1 \vee v_2) \wedge (v_1 \vee v_3)$ 3) ...
1
vote
2answers
24 views

Natural deduction proof for : p → ( c ∨ b) , b → s ⊢ ( p ∧ ¬s)→ c

I am trying to prove the following statement but I am getting stuck at the 6th line and I'm unsure how to continue. p → ( c ∨ b) , b → s ⊢ ( p ∧ ¬s)→ c p → ( c ∨ b) (premise) b → s (premise) ...
1
vote
1answer
80 views

Logical Notations for Mathematical Statements

I'm studying discrete mathematics and I'm faced with a problem of converting a few descriptive mathematical statements into logical notation. Any help would be appreciated. Thank you. a) Any ...
0
votes
3answers
58 views

Proving $(p \oplus q) \oplus r=p \oplus (q \oplus r)$

I was assigned to prove the associative law on xor. $(p \oplus q) \oplus r=p \oplus (q \oplus r)$ I'm sure $(p\oplus q)=(p∧¬q)∨(¬p∧q)$ But I got stuck on $(p \oplus q) \oplus ...
2
votes
1answer
46 views

Creating a proposition from a truth table using only ~ ⋀ and v

I have to find a simple expression for the third column in the truth table using only the logical connectives I've mention above. There are two questions that are involved here. Problem 1: Truth ...