{"id":2952,"date":"2025-06-06T07:17:21","date_gmt":"2025-06-06T07:17:21","guid":{"rendered":"https:\/\/diznr.com\/?p=2952"},"modified":"2025-06-06T07:17:21","modified_gmt":"2025-06-06T07:17:21","slug":"implication-concept-discrete-mathematics-previous-year-paper-gate-2020-the-resolution-following","status":"publish","type":"post","link":"https:\/\/www.reilsolar.com\/pdf\/implication-concept-discrete-mathematics-previous-year-paper-gate-2020-the-resolution-following\/","title":{"rendered":"Implication Concept Discrete mathematics previous year paper – GATE 2025- The following resolution."},"content":{"rendered":"

Implication Concept Discrete mathematics previous year paper – GATE 2025- The following resolution.<\/p>\n

[fvplayer id=”186″]<\/p>\n

\u00a0Implication Concept in Discrete Mathematics – GATE 2025<\/strong><\/h3>\n

\u00a0What is an Implication?<\/strong><\/h4>\n

In propositional logic<\/strong>, an implication<\/strong> is a logical statement of the form:<\/p>\n

P\u2192QP \\rightarrow Q<\/span>P<\/span>\u2192<\/span><\/span>Q<\/span><\/span><\/span><\/span><\/span><\/p>\n

This means “If PP<\/span>P<\/span><\/span><\/span><\/span> is true, then QQ<\/span>Q<\/span><\/span><\/span><\/span> must also be true.”<\/strong><\/p>\n

Truth Table for Implication (P\u2192QP \\rightarrow Q<\/span>P<\/span>\u2192<\/span><\/span>Q<\/span><\/span><\/span><\/span>)<\/strong><\/p>\n

\n\n\n\n\n\n\n\n\n
PP<\/span>P<\/span><\/span><\/span><\/span><\/th>\nQQ<\/span>Q<\/span><\/span><\/span><\/span><\/th>\nP\u2192QP \\rightarrow Q<\/span>P<\/span>\u2192<\/span><\/span>Q<\/span><\/span><\/span><\/span><\/th>\n<\/tr>\n<\/thead>\n
T<\/td>\nT<\/td>\nT<\/td>\n<\/tr>\n
T<\/td>\nF<\/td>\nF<\/td>\n<\/tr>\n
F<\/td>\nT<\/td>\nT<\/td>\n<\/tr>\n
F<\/td>\nF<\/td>\nT<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n

Key Observations:<\/strong><\/p>\n

    \n
  1. If PP<\/span>P<\/span><\/span><\/span><\/span> is true<\/strong> and QQ<\/span>Q<\/span><\/span><\/span><\/span> is false<\/strong>, then P\u2192QP \\rightarrow Q<\/span>P<\/span>\u2192<\/span><\/span>Q<\/span><\/span><\/span><\/span> is false<\/strong>.<\/li>\n
  2. In all other cases, P\u2192QP \\rightarrow Q<\/span>P<\/span>\u2192<\/span><\/span>Q<\/span><\/span><\/span><\/span> is true<\/strong>.<\/li>\n
  3. When PP<\/span>P<\/span><\/span><\/span><\/span> is false<\/strong>, the implication P\u2192QP \\rightarrow Q<\/span>P<\/span>\u2192<\/span><\/span>Q<\/span><\/span><\/span><\/span> is always true<\/strong>, regardless of QQ<\/span>Q<\/span><\/span><\/span><\/span>.<\/li>\n<\/ol>\n

    \u00a0Important Properties of Implication<\/strong><\/h3>\n

    Contrapositive:<\/strong><\/p>\n

    P\u2192Q\u2261\u00acQ\u2192\u00acPP \\rightarrow Q \\equiv \\neg Q \\rightarrow \\neg P<\/span>P<\/span>\u2192<\/span><\/span>Q<\/span>\u2261<\/span><\/span>\u00ac<\/span>Q<\/span>\u2192<\/span><\/span>\u00ac<\/span>P<\/span><\/span><\/span><\/span><\/span><\/p>\n

    (Logically equivalent, used in proofs)<\/p>\n

    Inverse:<\/strong><\/p>\n

    \u00acP\u2192\u00acQ\\neg P \\rightarrow \\neg Q<\/span>\u00ac<\/span>P<\/span>\u2192<\/span><\/span>\u00ac<\/span>Q<\/span><\/span><\/span><\/span><\/span><\/p>\n

    (Not logically equivalent to P\u2192QP \\rightarrow Q<\/span>P<\/span>\u2192<\/span><\/span>Q<\/span><\/span><\/span><\/span>)<\/p>\n

    Converse:<\/strong><\/p>\n

    Q\u2192PQ \\rightarrow P<\/span>Q<\/span>\u2192<\/span><\/span>P<\/span><\/span><\/span><\/span><\/span><\/p>\n

    (Not logically equivalent to P\u2192QP \\rightarrow Q<\/span>P<\/span>\u2192<\/span><\/span>Q<\/span><\/span><\/span><\/span>)<\/p>\n

    Material Implication:<\/strong><\/p>\n

    P\u2192Q\u2261\u00acP\u2228QP \\rightarrow Q \\equiv \\neg P \\lor Q<\/span>P<\/span>\u2192<\/span><\/span>Q<\/span>\u2261<\/span><\/span>\u00ac<\/span>P<\/span>\u2228<\/span><\/span>Q<\/span><\/span><\/span><\/span><\/span><\/p>\n

    (Can be rewritten in terms of OR operation)<\/p>\n

    \u00a0GATE 2025 Previous Year Question on Implication<\/strong><\/h3>\n

    Question:<\/strong><\/h4>\n

    Given three propositions P,Q,RP, Q, R<\/span>P<\/span>,<\/span>Q<\/span>,<\/span>R<\/span><\/span><\/span><\/span>, which of the following is a valid logical equivalence?<\/p>\n

    (A) (P\u2192Q)\u2228R\u2261(P\u2228R)\u2192(Q\u2228R)(P \\rightarrow Q) \\lor R \\equiv (P \\lor R) \\rightarrow (Q \\lor R)<\/span>(<\/span>P<\/span>\u2192<\/span><\/span>Q<\/span>)<\/span>\u2228<\/span><\/span>R<\/span>\u2261<\/span><\/span>(<\/span>P<\/span>\u2228<\/span><\/span>R<\/span>)<\/span>\u2192<\/span><\/span>(<\/span>Q<\/span>\u2228<\/span><\/span>R<\/span>)<\/span><\/span><\/span><\/span>
    (B) (P\u2192Q)\u2228R\u2261(P\u2192(Q\u2228R))(P \\rightarrow Q) \\lor R \\equiv (P \\rightarrow (Q \\lor R))<\/span>(<\/span>P<\/span>\u2192<\/span><\/span>Q<\/span>)<\/span>\u2228<\/span><\/span>R<\/span>\u2261<\/span><\/span>(<\/span>P<\/span>\u2192<\/span><\/span>(<\/span>Q<\/span>\u2228<\/span><\/span>R<\/span>))<\/span><\/span><\/span><\/span>
    (C) (P\u2192Q)\u2228R\u2261((P\u2228R)\u2192Q)(P \\rightarrow Q) \\lor R \\equiv ((P \\lor R) \\rightarrow Q)<\/span>(<\/span>P<\/span>\u2192<\/span><\/span>Q<\/span>)<\/span>\u2228<\/span><\/span>R<\/span>\u2261<\/span><\/span>((<\/span>P<\/span>\u2228<\/span><\/span>R<\/span>)<\/span>\u2192<\/span><\/span>Q<\/span>)<\/span><\/span><\/span><\/span>
    (D) (P\u2192Q)\u2228R\u2261(\u00acP\u2228(Q\u2228R))(P \\rightarrow Q) \\lor R \\equiv (\\neg P \\lor (Q \\lor R))<\/span>(<\/span>P<\/span>\u2192<\/span><\/span>Q<\/span>)<\/span>\u2228<\/span><\/span>R<\/span>\u2261<\/span><\/span>(<\/span>\u00ac<\/span>P<\/span>\u2228<\/span><\/span>(<\/span>Q<\/span>\u2228<\/span><\/span>R<\/span>))<\/span><\/span><\/span><\/span><\/p>\n

    Solution Approach:<\/strong><\/h4>\n

    We use Material Implication<\/strong>:<\/p>\n

    P\u2192Q\u2261\u00acP\u2228QP \\rightarrow Q \\equiv \\neg P \\lor Q<\/span>P<\/span>\u2192<\/span><\/span>Q<\/span>\u2261<\/span><\/span>\u00ac<\/span>P<\/span>\u2228<\/span><\/span>Q<\/span><\/span><\/span><\/span><\/span><\/p>\n

    Now, rewriting option (D):<\/strong><\/p>\n

    (P\u2192Q)\u2228R=(\u00acP\u2228Q)\u2228R(P \\rightarrow Q) \\lor R = (\\neg P \\lor Q) \\lor R<\/span>(<\/span>P<\/span>\u2192<\/span><\/span>Q<\/span>)<\/span>\u2228<\/span><\/span>R<\/span>=<\/span><\/span>(<\/span>\u00ac<\/span>P<\/span>\u2228<\/span><\/span>Q<\/span>)<\/span>\u2228<\/span><\/span>R<\/span><\/span><\/span><\/span><\/span> =\u00acP\u2228(Q\u2228R)= \\neg P \\lor (Q \\lor R)<\/span>=<\/span><\/span>\u00ac<\/span>P<\/span>\u2228<\/span><\/span>(<\/span>Q<\/span>\u2228<\/span><\/span>R<\/span>)<\/span><\/span><\/span><\/span><\/span><\/p>\n

    Correct Answer:<\/strong> Option (D)<\/strong><\/p>\n

    \u00a0Conclusion<\/strong><\/h3>\n

    Implication (P\u2192QP \\rightarrow Q<\/span>P<\/span>\u2192<\/span><\/span>Q<\/span><\/span><\/span><\/span>) is False only when PP<\/span>P<\/span><\/span><\/span><\/span> is True and QQ<\/span>Q<\/span><\/span><\/span><\/span> is False.<\/strong>
    Logical Equivalences:<\/strong><\/p>\n